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

wv = [tuple(map(int, input().split()))for _ in range(N)]

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

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

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

        if 0 <= j-wv[i-1][0]:

            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]]+wv[i-1][1])

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



print((dp[-1][-1]))
n, w = list(map(int, input().split()))

weights, values = list(zip(*[tuple(map(int, input().split()))for _ in range(n)]))

dp = [0]*(w+1)

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

    for j in reversed(list(range(1, w+1))):

        if j-weights[i-1] < 0:

            continue

        dp[j] = max(dp[j], dp[j-weights[i-1]]+values[i-1])

print((dp[-1]))
N, W = list(map(int, input().split()))
wv = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(1, N + 1):
    for j in range(1, W + 1):
        if 0 <= j - wv[i - 1][0]:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wv[i - 1][0]] + wv[i - 1][1])
        dp[i][j] = max(dp[i - 1][j], dp[i][j])
print((dp[-1][-1]))

n, w = list(map(int, input().split()))
weights, values = list(zip(*[tuple(map(int, input().split())) for _ in range(n)]))
dp = [0] * (w + 1)
for i in range(1, n + 1):
    for j in reversed(list(range(1, w + 1))):
        if j - weights[i - 1] < 0:
            continue
        dp[j] = max(dp[j], dp[j - weights[i - 1]] + values[i - 1])
print((dp[-1]))

-N, W = list(map(int, input().split())) -wv = [tuple(map(int, input().split())) for _ in range(N)] -dp = [[0] * (W + 1) for _ in range(N + 1)] -for i in range(1, N + 1): -    for j in range(1, W + 1): -        if 0 <= j - wv[i - 1][0]: -            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wv[i - 1][0]] + wv[i - 1][1]) -        dp[i][j] = max(dp[i - 1][j], dp[i][j]) -print((dp[-1][-1])) +n, w = list(map(int, input().split())) +weights, values = list(zip(*[tuple(map(int, input().split())) for _ in range(n)])) +dp = [0] * (w + 1) +for i in range(1, n + 1): +    for j in reversed(list(range(1, w + 1))): +        if j - weights[i - 1] < 0: +            continue +        dp[j] = max(dp[j], dp[j - weights[i - 1]] + values[i - 1]) +print((dp[-1]))