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

w_list = []

v_list = []

for i in range(N):

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

    w_list.append(w)

    v_list.append(v)

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

for i in range(N):

    w = w_list[i]

    v = v_list[i]

    for j in range(W+1):

        if j-w >= 0:

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

        else:

            dp[i][j] = dp[i-1][j]

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

w_list = []

v_list = []

for _ in range(N):

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

    w_list.append(w)

    v_list.append(v)

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

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

    w = w_list[i-1]

    v = v_list[i-1]

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

        if j-w >= 0:

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

        else:

            dp[i][j] = dp[i-1][j]

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

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

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