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

vw=[list(map(int,input().split())) for i in range(N)]

dp=[[0]*(W+1) for _ in range(N+1)]

for i in range(N):

    for j in range(W+1):

        if vw[i][1]>j:

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

        else:

            dp[i+1][j]=max(dp[i][j],dp[i+1][j-vw[i][1]]+vw[i][0])

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

vw=[list(map(int,input().split())) for _ in range(n)]

dp=[0]*(w+1)

for i in range(n):

    for j in range(vw[i][1],w+1):

        dp[j]=max(dp[j],dp[j-vw[i][1]]+vw[i][0])

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

n, w = list(map(int, input().split()))
vw = [list(map(int, input().split())) for _ in range(n)]
dp = [0] * (w + 1)
for i in range(n):
    for j in range(vw[i][1], w + 1):
        dp[j] = max(dp[j], dp[j - vw[i][1]] + vw[i][0])
print((dp[w]))

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