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

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

dp=[[0]*(w+1) for _ in range(2)]

for i in range(n):

    for j in range(w+1):

        if j<vw[i][1]:

            dp[(i+1)&1][j]=dp[i&1][j]

        else:

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

print((dp[n&1][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(w,vw[i][1]-1,-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 _ in range(n)]
dp = [[0] * (w + 1) for _ in range(2)]
for i in range(n):
    for j in range(w + 1):
        if j < vw[i][1]:
            dp[(i + 1) & 1][j] = dp[i & 1][j]
        else:
            dp[(i + 1) & 1][j] = max(dp[i & 1][j], dp[i & 1][j - vw[i][1]] + vw[i][0])
print((dp[n & 1][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(w, vw[i][1] - 1, -1):
        dp[j] = max(dp[j], dp[j - vw[i][1]] + vw[i][0])
print((dp[w]))

-dp = [[0] * (w + 1) for _ in range(2)] +dp = [0] * (w + 1) -    for j in range(w + 1): -        if j < vw[i][1]: -            dp[(i + 1) & 1][j] = dp[i & 1][j] -        else: -            dp[(i + 1) & 1][j] = max(dp[i & 1][j], dp[i & 1][j - vw[i][1]] + vw[i][0]) -print((dp[n & 1][w])) +    for j in range(w, vw[i][1] - 1, -1): +        dp[j] = max(dp[j], dp[j - vw[i][1]] + vw[i][0]) +print((dp[w]))