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

pair = [tuple(map(int, input().split(' '))) for _ in range(N)]

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

for i in range(N):

    for sum_w in range(W+1):

        if sum_w >= pair[i][0]:

            dp[i+1][sum_w] = max(dp[i][sum_w], dp[i][sum_w-pair[i][0]] + pair[i][1])

        else:

            dp[i+1][sum_w] = dp[i][sum_w]

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

W = [0] * N

V = [0] * N

for i in range(N):

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

    W[i] = w

    V[i] = v

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

for n in range(1, N+1):

    w = W[n-1]

    v = V[n-1]

    for sum_w in range(WW+1):

        if sum_w <= WW - w:

            # n番目の商品を選ぶ

            dp[n][sum_w+w] = max(dp[n-1][sum_w] + v, dp[n][sum_w+w])

        dp[n][sum_w] = max(dp[n-1][sum_w], dp[n][sum_w])

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

N, WW = list(map(int, input().split()))
W = [0] * N
V = [0] * N
for i in range(N):
    w, v = list(map(int, input().split()))
    W[i] = w
    V[i] = v
dp = [[0] * (WW + 1) for _ in range(N + 1)]
for n in range(1, N + 1):
    w = W[n - 1]
    v = V[n - 1]
    for sum_w in range(WW + 1):
        if sum_w <= WW - w:
            # n番目の商品を選ぶ
            dp[n][sum_w + w] = max(dp[n - 1][sum_w] + v, dp[n][sum_w + w])
        dp[n][sum_w] = max(dp[n - 1][sum_w], dp[n][sum_w])
print((dp[-1][-1]))

-N, W = list(map(int, input().split(" "))) -pair = [tuple(map(int, input().split(" "))) for _ in range(N)] -dp = [[0] * (W + 1) for _ in range(N + 1)] +N, WW = list(map(int, input().split())) +W = [0] * N +V = [0] * N -    for sum_w in range(W + 1): -        if sum_w >= pair[i][0]: -            dp[i + 1][sum_w] = max(dp[i][sum_w], dp[i][sum_w - pair[i][0]] + pair[i][1]) -        else: -            dp[i + 1][sum_w] = dp[i][sum_w] +    w, v = list(map(int, input().split())) +    W[i] = w +    V[i] = v +dp = [[0] * (WW + 1) for _ in range(N + 1)] +for n in range(1, N + 1): +    w = W[n - 1] +    v = V[n - 1] +    for sum_w in range(WW + 1): +        if sum_w <= WW - w: +            # n番目の商品を選ぶ +            dp[n][sum_w + w] = max(dp[n - 1][sum_w] + v, dp[n][sum_w + w]) +        dp[n][sum_w] = max(dp[n - 1][sum_w], dp[n][sum_w])