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):

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

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



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)
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):
        dp[j] = max(temp[j - w] + v, temp[j])
    temp[0 : W + 1] = dp[0 : W + 1]
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]))

-        dp[j] = max(temp[j - w] + v, temp[j]) +        x = v + temp[j - w] +        if x > temp[j]: +            dp[j] = x