def get_max_value(n, W, v, w):

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

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

		wt = w[i-1]

		vl = v[i-1]

		for j in range(W+1):

			if wt > j:

				dp[i][j]=dp[i-1][j]

			else:

				dp[i][j]=max(dp[i-1][j], dp[i-1][j-wt]+vl)

	return dp[n][W]



n, W = list(map(int, input().split()))

v = [0]*n

w = [0]*n

for i in range(n):

	v[i], w[i] = list(map(int, input().split()))

print((get_max_value(n, W, v, w)))



def get_max_value(n, W, v, w):

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

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

		wt = w[i-1]

		vl = v[i-1]

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

			if wt > j:

				dp[i][j]=dp[i-1][j]

			else:

				dp[i][j]=max(dp[i-1][j], dp[i-1][j-wt]+vl)

	return dp[n][W]



n, W = list(map(int, input().split()))

v = [0]*n

w = [0]*n

for i in range(n):

	v[i], w[i] = list(map(int, input().split()))

print((get_max_value(n, W, v, w)))



def get_max_value(n, W, v, w):
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
    for i in range(1, n + 1):
        wt = w[i - 1]
        vl = v[i - 1]
        for j in range(W + 1):
            if wt > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wt] + vl)
    return dp[n][W]


n, W = list(map(int, input().split()))
v = [0] * n
w = [0] * n
for i in range(n):
    v[i], w[i] = list(map(int, input().split()))
print((get_max_value(n, W, v, w)))

def get_max_value(n, W, v, w):
    dp = [[0 for x in range(W + 1)] for x in range(n + 1)]
    for i in range(1, n + 1):
        wt = w[i - 1]
        vl = v[i - 1]
        for j in range(1, W + 1):
            if wt > j:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wt] + vl)
    return dp[n][W]


n, W = list(map(int, input().split()))
v = [0] * n
w = [0] * n
for i in range(n):
    v[i], w[i] = list(map(int, input().split()))
print((get_max_value(n, W, v, w)))

-        for j in range(W + 1): +        for j in range(1, W + 1):