(N, W), *D = [list(map(int, o.split())) for o in open(0)]

w, v = 0, 1

dp = [[0]*-~W for _ in [0]*-~N]

for i in range(N):

  for j in range(W + 1):

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

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

dp = [0]*-~W

for _ in [None]*N:

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

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

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

print((max(dp)))
(N, W), *D = [list(map(int, o.split())) for o in open(0)]
w, v = 0, 1
dp = [[0] * -~W for _ in [0] * -~N]
for i in range(N):
    for j in range(W + 1):
        dp[i + 1][j] = max(dp[i][j], (dp[i][j - D[i][w]] + D[i][v]) * (j >= D[i][w]))
print((dp[N][W]))

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

-(N, W), *D = [list(map(int, o.split())) for o in open(0)] -w, v = 0, 1 -dp = [[0] * -~W for _ in [0] * -~N] -for i in range(N): -    for j in range(W + 1): -        dp[i + 1][j] = max(dp[i][j], (dp[i][j - D[i][w]] + D[i][v]) * (j >= D[i][w])) -print((dp[N][W])) +N, W = list(map(int, input().split())) +dp = [0] * -~W +for _ in [None] * N: +    w, v = list(map(int, input().split())) +    for j in range(W, w - 1, -1): +        dp[j] = max(dp[j], dp[j - w] + v) +print((max(dp)))