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

w = [0] * N

v = [0] * N

for i in range(N):

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



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



for i in range(N):

    for sum_w in range(W+1):

        if w[i] <= sum_w:

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

        dp[i+1][sum_w] = max(dp[i][sum_w], dp[i+1][sum_w])



print((dp[N][W]))
N, W = list(map(int, input().split()))

w = [0] * N

v = [0] * N

for i in range(N):

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



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

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

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

        if w[i-1] <= s:

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

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



print((dp[N][W]))

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

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

-dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)] -for i in range(N): -    for sum_w in range(W + 1): -        if w[i] <= sum_w: -            dp[i + 1][sum_w] = max(dp[i][sum_w], dp[i][sum_w - w[i]] + v[i]) -        dp[i + 1][sum_w] = max(dp[i][sum_w], dp[i + 1][sum_w]) +dp = [[0] * (W + 1) for i in range(N + 1)] +for i in range(1, N + 1): +    for s in range(1, W + 1): +        if w[i - 1] <= s: +            dp[i][s] = max(dp[i][s], dp[i - 1][s - w[i - 1]] + v[i - 1]) +        dp[i][s] = max(dp[i][s], dp[i - 1][s])