num,weight = (int(n) for n in input().split(" "))

query = []

for n in range(num):

    query.append([int(n) for n in input().split(" ")])

nap = [[0 for n in range(weight + 1)] for m in range(num + 1)]

for n in range(num):

    for w in range(weight + 1):



        if query[n][1] <= w:

            nap[n + 1][w] = max(nap[n][w-query[n][1]] + query[n][0],nap[n][w])

        else:

            nap[n + 1][w] = nap[n][w]

print((nap[num][weight]))
import copy

length, capacity = list(map(int, input().split(" ")))

nap = []

for _ in range(length):

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

    nap.append([v, w])

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



for i, (v, w) in enumerate(nap):

    new_dp = dp[::]

    if w <= capacity:

        new_dp[w] = max(v, dp[w])

    for j, now_v in enumerate(dp):

        if now_v and j + w <= capacity:

            new_dp[j + w] = max(dp[j + w], now_v + v)

    dp = new_dp

answer = 0

for v in dp:

    answer = max(answer, v)

print(answer)



num, weight = (int(n) for n in input().split(" "))
query = []
for n in range(num):
    query.append([int(n) for n in input().split(" ")])
nap = [[0 for n in range(weight + 1)] for m in range(num + 1)]
for n in range(num):
    for w in range(weight + 1):
        if query[n][1] <= w:
            nap[n + 1][w] = max(nap[n][w - query[n][1]] + query[n][0], nap[n][w])
        else:
            nap[n + 1][w] = nap[n][w]
print((nap[num][weight]))

import copy

length, capacity = list(map(int, input().split(" ")))
nap = []
for _ in range(length):
    v, w = list(map(int, input().split(" ")))
    nap.append([v, w])
dp = [0 for n in range(capacity + 1)]
for i, (v, w) in enumerate(nap):
    new_dp = dp[::]
    if w <= capacity:
        new_dp[w] = max(v, dp[w])
    for j, now_v in enumerate(dp):
        if now_v and j + w <= capacity:
            new_dp[j + w] = max(dp[j + w], now_v + v)
    dp = new_dp
answer = 0
for v in dp:
    answer = max(answer, v)
print(answer)

-num, weight = (int(n) for n in input().split(" ")) -query = [] -for n in range(num): -    query.append([int(n) for n in input().split(" ")]) -nap = [[0 for n in range(weight + 1)] for m in range(num + 1)] -for n in range(num): -    for w in range(weight + 1): -        if query[n][1] <= w: -            nap[n + 1][w] = max(nap[n][w - query[n][1]] + query[n][0], nap[n][w]) -        else: -            nap[n + 1][w] = nap[n][w] -print((nap[num][weight])) +import copy + +length, capacity = list(map(int, input().split(" "))) +nap = [] +for _ in range(length): +    v, w = list(map(int, input().split(" "))) +    nap.append([v, w]) +dp = [0 for n in range(capacity + 1)] +for i, (v, w) in enumerate(nap): +    new_dp = dp[::] +    if w <= capacity: +        new_dp[w] = max(v, dp[w]) +    for j, now_v in enumerate(dp): +        if now_v and j + w <= capacity: +            new_dp[j + w] = max(dp[j + w], now_v + v) +    dp = new_dp +answer = 0 +for v in dp: +    answer = max(answer, v) +print(answer)