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

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

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

for i in range(n):

    for j in range(w+1):

        weight,value=a[i]

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

        if j+weight<=w:

            dp[i+1][j+weight]=max(dp[i][j+weight],dp[i][j]+value)

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

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

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

for i in range(n):

    weight,value=a[i]

    for j in range(W+1):

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

        if j+weight<=W:

            dp[i+1][j+weight]=max(dp[i][j+weight],dp[i][j]+value)

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

n, W = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
for i in range(n):
    weight, value = a[i]
    for j in range(W + 1):
        dp[i + 1][j] = max(dp[i][j], dp[i + 1][j])
        if j + weight <= W:
            dp[i + 1][j + weight] = max(dp[i][j + weight], dp[i][j] + value)
print((dp[-1][-1]))

-n, w = list(map(int, input().split())) +n, W = list(map(int, input().split())) -dp = [[0 for _ in range(w + 1)] for _ in range(n + 1)] +dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)] -    for j in range(w + 1): -        weight, value = a[i] +    weight, value = a[i] +    for j in range(W + 1): -        if j + weight <= w: +        if j + weight <= W: