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

VW = [list(map(int, input().split())) for i in range(N)]

# N番目までの品物からWを超えないように選んだ時の最大価値合計

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



for i in range(N):

    for j in range(W+1):

        if VW[i][1] > j:

            dp[i+1][j] = dp[i][j]

        else:

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



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

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

v = []

w = []

for i in range(N):

    vv, ww = list(map(int, input().split()))

    v.append(vv)

    w.append(ww)



# dp[i]:重さiを超えないように選んだ時の最大価値合計

dp = [0] * (W+1)



for i in range(N):

    for j in range(W, w[i]-1, -1):

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



print((dp[W]))





N, W = list(map(int, input().split()))
VW = [list(map(int, input().split())) for i in range(N)]
# N番目までの品物からWを超えないように選んだ時の最大価値合計
dp = [[0] * (W + 1) for i in range(N + 1)]
for i in range(N):
    for j in range(W + 1):
        if VW[i][1] > j:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - VW[i][1]] + VW[i][0])
print((dp[N][W]))

N, W = list(map(int, input().split()))
v = []
w = []
for i in range(N):
    vv, ww = list(map(int, input().split()))
    v.append(vv)
    w.append(ww)
# dp[i]:重さiを超えないように選んだ時の最大価値合計
dp = [0] * (W + 1)
for i in range(N):
    for j in range(W, w[i] - 1, -1):
        dp[j] = max(dp[j], dp[j - w[i]] + v[i])
print((dp[W]))

-VW = [list(map(int, input().split())) for i in range(N)] -# N番目までの品物からWを超えないように選んだ時の最大価値合計 -dp = [[0] * (W + 1) for i in range(N + 1)] +v = [] +w = [] -    for j in range(W + 1): -        if VW[i][1] > j: -            dp[i + 1][j] = dp[i][j] -        else: -            dp[i + 1][j] = max(dp[i][j], dp[i][j - VW[i][1]] + VW[i][0]) -print((dp[N][W])) +    vv, ww = list(map(int, input().split())) +    v.append(vv) +    w.append(ww) +# dp[i]:重さiを超えないように選んだ時の最大価値合計 +dp = [0] * (W + 1) +for i in range(N): +    for j in range(W, w[i] - 1, -1): +        dp[j] = max(dp[j], dp[j - w[i]] + v[i]) +print((dp[W]))