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

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



for j in range(N):

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

    for k in range(W + 1):

        if k >= w:

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

        else:

            dp[j+1][k] = dp[j][k]



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

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

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

for i in range(N):

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

    for j in range(W+1):

        if w + j <= W:

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

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

        else:

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



print((max(dp[N])))

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

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

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