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

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

for i in range(N):

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

    for j in range(W+1):

        if j < w:

            dp[i+1][j] = dp[i][j]

        else:

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

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

dp = [0]*(W+1)

for _ in range(N):

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

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

        if i-w < 0:

            continue

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

print((max(dp)))

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

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

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