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(1, W+1):

        if w <= j and v + temp[j-w] > temp[j]:

            dp[j] = temp[j-w]+v

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

        if v + temp[j-w] > temp[j]:

            dp[j] = temp[j-w]+v

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

-    for j in range(1, W + 1): -        if w <= j and v + temp[j - w] > temp[j]: +    for j in range(w, W + 1): +        if v + temp[j - w] > temp[j]: