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

w=[0]*N

v=[0]*N

for i in range(N):

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

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

for i in range(N):

    for j in range(W+1):

        if j<w[i]:

            dp[i+1][j]=dp[i][j]

        else:

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

print((dp[N][W]))

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

w=[0]*N

v=[0]*N

for i in range(N):

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

dp=[0]*(W+1)

for i in range(N):

    j=W

    while j>=w[i]:

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

        j-=1

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

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

-dp = [[0 for i in range(W + 1)] for j in range(N + 1)] +dp = [0] * (W + 1) -    for j in range(W + 1): -        if j < w[i]: -            dp[i + 1][j] = dp[i][j] -        else: -            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]) -print((dp[N][W])) +    j = W +    while j >= w[i]: +        dp[j] = max(dp[j], dp[j - w[i]] + v[i]) +        j -= 1 +print((dp[W]))