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 = [[int(0) for i in range(W+1)] for i in range(N+1)]

ans = int(0)

dp[0][0] = 0





for i in range(N):

    for j in range(W+1):

        if w[i]<=j:

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

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



ans = dp[N][W]



print(ans)
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)]

ans = int(0)

dp[0][0] = 0



for i in range(N):

    for j in range(W+1):

        if w[i]<=j:

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

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



ans = dp[N][W]



print(ans)
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 = [[int(0) for i in range(W + 1)] for i in range(N + 1)]
ans = int(0)
dp[0][0] = 0
for i in range(N):
    for j in range(W + 1):
        if w[i] <= j:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
ans = dp[N][W]
print(ans)

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)]
ans = int(0)
dp[0][0] = 0
for i in range(N):
    for j in range(W + 1):
        if w[i] <= j:
            dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w[i]] + v[i])
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
ans = dp[N][W]
print(ans)

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