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 _ in range(N+1)]

# dp[i][sum_w]

# i-1番目までの品物から重さがsum_wを超えないように選んだ時の価値の総和

# sum_w = 0, 1, 2, ... ,W



for i in range(N):

    for sum_w in range(W+1):

        if sum_w - w[i] >= 0:

            dp[i+1][sum_w] = dp[i][sum_w - w[i]] + v[i]



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

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

w, v = [0]*n, [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)]

#i品目までの中から重さwを超えないように選んだときの価値の総和の最大値

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

    for j in range(W+1):

        if j - w[i-1] >= 0:

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

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

print((max(dp[n])))



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 _ in range(N + 1)]
# dp[i][sum_w]
# i-1番目までの品物から重さがsum_wを超えないように選んだ時の価値の総和
# sum_w = 0, 1, 2, ... ,W
for i in range(N):
    for sum_w in range(W + 1):
        if sum_w - w[i] >= 0:
            dp[i + 1][sum_w] = dp[i][sum_w - w[i]] + v[i]
        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w])
print((dp[N][W]))

n, W = list(map(int, input().split()))
w, v = [0] * n, [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)]
# i品目までの中から重さwを超えないように選んだときの価値の総和の最大値
for i in range(1, n + 1):
    for j in range(W + 1):
        if j - w[i - 1] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i - 1]] + v[i - 1])
        dp[i][j] = max(dp[i][j], dp[i - 1][j])
print((max(dp[n])))

-N, W = list(map(int, input().split())) -w = [0] * N -v = [0] * N -for i in range(N): +n, W = list(map(int, input().split())) +w, v = [0] * n, [0] * n +for i in range(n): -dp = [[0] * (W + 1) for _ in range(N + 1)] -# dp[i][sum_w] -# i-1番目までの品物から重さがsum_wを超えないように選んだ時の価値の総和 -# sum_w = 0, 1, 2, ... ,W -for i in range(N): -    for sum_w in range(W + 1): -        if sum_w - w[i] >= 0: -            dp[i + 1][sum_w] = dp[i][sum_w - w[i]] + v[i] -        dp[i + 1][sum_w] = max(dp[i + 1][sum_w], dp[i][sum_w]) -print((dp[N][W])) +dp = [[0] * (W + 1) for i in range(n + 1)] +# i品目までの中から重さwを超えないように選んだときの価値の総和の最大値 +for i in range(1, n + 1): +    for j in range(W + 1): +        if j - w[i - 1] >= 0: +            dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i - 1]] + v[i - 1]) +        dp[i][j] = max(dp[i][j], dp[i - 1][j]) +print((max(dp[n])))