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

dp = [0]*(W+1)

temp = [0]*(W+1)



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

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

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

        x = v+temp[j-w]

        if x > temp[j]: dp[j] = x



    temp[0:W+1] = dp[0:W+1]



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

dp = [0]*(W+1)



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

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

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

        x = v+dp[j-w]

        if x > dp[j]: dp[j] = x



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

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

-temp = [0] * (W + 1) -    for j in range(w, W + 1): -        x = v + temp[j - w] -        if x > temp[j]: +    for j in range(W, w - 1, -1): +        x = v + dp[j - w] +        if x > dp[j]: -    temp[0 : W + 1] = dp[0 : W + 1]