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)



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

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

for l in range(length):

    v, w = (int(n) for n in input().split(" ") )

    temp = dp[:]

    for i, d in enumerate(dp):

        if d and i + w <= weight:

            temp[i + w] = max(d + v, dp[i + w])

    dp = temp

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

    # print(dp)

print((max(dp)))

            

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)

length, weight = (int(n) for n in input().split(" "))
dp = [0 for n in range(weight + 1)]
for l in range(length):
    v, w = (int(n) for n in input().split(" "))
    temp = dp[:]
    for i, d in enumerate(dp):
        if d and i + w <= weight:
            temp[i + w] = max(d + v, dp[i + w])
    dp = temp
    dp[w] = max(v, dp[w])
    # print(dp)
print((max(dp)))

-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) +length, weight = (int(n) for n in input().split(" ")) +dp = [0 for n in range(weight + 1)] +for l in range(length): +    v, w = (int(n) for n in input().split(" ")) +    temp = dp[:] +    for i, d in enumerate(dp): +        if d and i + w <= weight: +            temp[i + w] = max(d + v, dp[i + w]) +    dp = temp +    dp[w] = max(v, dp[w]) +    # print(dp) +print((max(dp)))