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

v = [0]*N;w = [0]*N



for i in range(N):

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



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

for i in range(N):

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

        if j<w[i]:

            value[i][j] = value[i-1][j]

        else:

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





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

v = [0]*N;w = [0]*N



for i in range(N):

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



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

for i in range(N):

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

        if j<w[i]:

            value[j] = value[j]

        else:

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



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

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

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