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)]

query = sorted(query,key = lambda x:x[1],reverse = True)

for n in range(num):

    for w in range(weight + 1):

        if w == 0:

            continue

        elif w >= query[n][1]:

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



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

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

dp = [0] * (cap + 1)

items = []

for _ in range(length):

    a, b = list(map(int, input().split(" ")))

    items.append([a, b])



for item in items:

    v, w = item

    temp_dp = copy.copy(dp)

    temp_dp[w] = max(temp_dp[w], v)

    for j in range(cap):

        if temp_dp[j] and w + j <= cap:

            temp_dp[w + j] = max(temp_dp[w + j], v + temp_dp[j])

    dp = temp_dp

answer = max(dp)

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)]
query = sorted(query, key=lambda x: x[1], reverse=True)
for n in range(num):
    for w in range(weight + 1):
        if w == 0:
            continue
        elif w >= query[n][1]:
            nap[n + 1][w] = max(
                nap[n + 1][w - query[n][1]] + query[n][0],
                nap[n][w - query[n][1]] + query[n][0],
                nap[n][w],
            )
print((nap[num][weight]))

import copy

length, cap = list(map(int, input().split(" ")))
dp = [0] * (cap + 1)
items = []
for _ in range(length):
    a, b = list(map(int, input().split(" ")))
    items.append([a, b])
for item in items:
    v, w = item
    temp_dp = copy.copy(dp)
    temp_dp[w] = max(temp_dp[w], v)
    for j in range(cap):
        if temp_dp[j] and w + j <= cap:
            temp_dp[w + j] = max(temp_dp[w + j], v + temp_dp[j])
    dp = temp_dp
answer = max(dp)
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)] -query = sorted(query, key=lambda x: x[1], reverse=True) -for n in range(num): -    for w in range(weight + 1): -        if w == 0: -            continue -        elif w >= query[n][1]: -            nap[n + 1][w] = max( -                nap[n + 1][w - query[n][1]] + query[n][0], -                nap[n][w - query[n][1]] + query[n][0], -                nap[n][w], -            ) -print((nap[num][weight])) +import copy + +length, cap = list(map(int, input().split(" "))) +dp = [0] * (cap + 1) +items = [] +for _ in range(length): +    a, b = list(map(int, input().split(" "))) +    items.append([a, b]) +for item in items: +    v, w = item +    temp_dp = copy.copy(dp) +    temp_dp[w] = max(temp_dp[w], v) +    for j in range(cap): +        if temp_dp[j] and w + j <= cap: +            temp_dp[w + j] = max(temp_dp[w + j], v + temp_dp[j]) +    dp = temp_dp +answer = max(dp) +print(answer)