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

dp = {}

for i in range(W + 1):

    dp[i] = 0

for i in range(N):

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

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

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

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

dp = [[0] * (W + 1)] * (N + 1)

for i in range(N):

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

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

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

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

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

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