from sys import stdin, stdout

rl = lambda: stdin.readline()

rll = lambda: stdin.readline().split()

rli = lambda: list(map(int, stdin.readline().split()))



INF, NINF = float('inf'), float('-inf')



def main():

	n, W = rli()

	weight = [0 for _ in range(n)]

	val = [0 for _ in range(n)]

	for i in range(n):

		w, v = rli()

		weight[i], val[i] = w, v

	#dp(i, j) = max val using items 1,...,i at 

	#			weight j



	dp = [[NINF for c in range(W+1)] for r in range(n+1)]

	for r in range(n+1):

		dp[r][0] = 0

	for c in range(W+1):

		dp[0][c] = 0

	for r in range(1, n+1):

		w, v = weight[r-1], val[r-1]

		for c in range(1, W+1):

			dp[r][c] = dp[r-1][c]

			if c - w >= 0:

				dp[r][c] = max(dp[r][c], dp[r-1][c], v + dp[r-1][c-w])

	print((dp[-1][-1]))

	stdout.close()



if __name__ == "__main__":

	main()
from sys import stdin, stdout

from collections import deque, defaultdict

import math as m



rl = lambda: stdin.readline()

rll = lambda: stdin.readline().split()

rli = lambda: list(map(int, stdin.readline().split()))



INF, NINF = float('inf'), float('-inf')



def main():

	n, W = rli()

	items = []

	for _ in range(n):

		w, v = rli()

		items.append((w, v))

	dp = [0 for _ in range(W + 1)]

	for w, v in items:

		for i in range(W, -1, -1):

			if i - w >= 0:

				dp[i] = max(dp[i], dp[i-w] + v)

	print((dp[-1]))

	stdout.close()



if __name__ == "__main__":

	main()
from sys import stdin, stdout

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: list(map(int, stdin.readline().split()))
INF, NINF = float("inf"), float("-inf")


def main():
    n, W = rli()
    weight = [0 for _ in range(n)]
    val = [0 for _ in range(n)]
    for i in range(n):
        w, v = rli()
        weight[i], val[i] = w, v
    # dp(i, j) = max val using items 1,...,i at
    # 			weight j
    dp = [[NINF for c in range(W + 1)] for r in range(n + 1)]
    for r in range(n + 1):
        dp[r][0] = 0
    for c in range(W + 1):
        dp[0][c] = 0
    for r in range(1, n + 1):
        w, v = weight[r - 1], val[r - 1]
        for c in range(1, W + 1):
            dp[r][c] = dp[r - 1][c]
            if c - w >= 0:
                dp[r][c] = max(dp[r][c], dp[r - 1][c], v + dp[r - 1][c - w])
    print((dp[-1][-1]))
    stdout.close()


if __name__ == "__main__":
    main()

from sys import stdin, stdout
from collections import deque, defaultdict
import math as m

rl = lambda: stdin.readline()
rll = lambda: stdin.readline().split()
rli = lambda: list(map(int, stdin.readline().split()))
INF, NINF = float("inf"), float("-inf")


def main():
    n, W = rli()
    items = []
    for _ in range(n):
        w, v = rli()
        items.append((w, v))
    dp = [0 for _ in range(W + 1)]
    for w, v in items:
        for i in range(W, -1, -1):
            if i - w >= 0:
                dp[i] = max(dp[i], dp[i - w] + v)
    print((dp[-1]))
    stdout.close()


if __name__ == "__main__":
    main()

+from collections import deque, defaultdict +import math as m -    weight = [0 for _ in range(n)] -    val = [0 for _ in range(n)] -    for i in range(n): +    items = [] +    for _ in range(n): -        weight[i], val[i] = w, v -    # dp(i, j) = max val using items 1,...,i at -    # 			weight j -    dp = [[NINF for c in range(W + 1)] for r in range(n + 1)] -    for r in range(n + 1): -        dp[r][0] = 0 -    for c in range(W + 1): -        dp[0][c] = 0 -    for r in range(1, n + 1): -        w, v = weight[r - 1], val[r - 1] -        for c in range(1, W + 1): -            dp[r][c] = dp[r - 1][c] -            if c - w >= 0: -                dp[r][c] = max(dp[r][c], dp[r - 1][c], v + dp[r - 1][c - w]) -    print((dp[-1][-1])) +        items.append((w, v)) +    dp = [0 for _ in range(W + 1)] +    for w, v in items: +        for i in range(W, -1, -1): +            if i - w >= 0: +                dp[i] = max(dp[i], dp[i - w] + v) +    print((dp[-1]))