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



v = [0]* N

w = [0]* N



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



for i in range(N):

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



def rec(i,j):

    if dp[i][j] != -1:

        return dp[i][j]

        

    if i == N:

        res = 0

    elif j < w[i]:

        res = rec(i+1, j)

    else:

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

    

    dp[i][j] = res

    

    return dp[i][j]

    

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



v = [0]* N

w = [0]* N



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



for k in range(N):

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



for i in range(N-1,-1,-1):

    for j in range(W+1):

        if j < w[i]:

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

        else:

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



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


def rec(i, j):
    if dp[i][j] != -1:
        return dp[i][j]
    if i == N:
        res = 0
    elif j < w[i]:
        res = rec(i + 1, j)
    else:
        res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i])
    dp[i][j] = res
    return dp[i][j]


print((rec(0, W)))

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

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