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

w = [0]*(N+1)

v = [0]*(N+1)

for i in range(1,N+1): w[i],v[i] = list(map(int,input().split()))



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

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

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

        if i < w[j]: dp[i][j] = dp[i][j-1]

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

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

w = [0]*(N+1)

v = [0]*(N+1)

for i in range(1,N+1): w[i],v[i] = list(map(int,input().split()))



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

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

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

        if j < w[i]: dp[i][j] = dp[i-1][j]

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

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

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

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