import sys

readline = sys.stdin.readline



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

a = [(v, w) for _ in [None]*N for v, w in (list(map(int, readline().split())),)]



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

dp[0][0] = 0



weight = {0}

for i in range(N):

    item_value, item_weight = a[i]

    for w in weight.copy():

        dp[i+1][w] = dp[i+1][w] if dp[i+1][w] > dp[i][w] else dp[i][w]

        nvalue = dp[i][w] + item_value

        if w+item_weight <= W:

            dp[i+1][w+item_weight] = nvalue if nvalue > dp[i+1][w+item_weight] else dp[i+1][w+item_weight]

            weight.add(w+item_weight)



print((max(dp[N])))
import sys

readline = sys.stdin.readline



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



dp = [0] * (W+1)



weights = {0}

add = weights.add

for i in range(N):

    item_v, item_w = list(map(int, readline().split()))

    for w in sorted(weights, reverse=True):

        if w+item_w <= W and dp[w+item_w] < dp[w] + item_v:

            dp[w+item_w] = dp[w] + item_v

            add(w+item_w)



print((max(dp)))
import sys

readline = sys.stdin.readline
N, W = list(map(int, readline().split()))
a = [(v, w) for _ in [None] * N for v, w in (list(map(int, readline().split())),)]
dp = [[0] * (W + 1) for _ in [None] * (N + 1)]
dp[0][0] = 0
weight = {0}
for i in range(N):
    item_value, item_weight = a[i]
    for w in weight.copy():
        dp[i + 1][w] = dp[i + 1][w] if dp[i + 1][w] > dp[i][w] else dp[i][w]
        nvalue = dp[i][w] + item_value
        if w + item_weight <= W:
            dp[i + 1][w + item_weight] = (
                nvalue
                if nvalue > dp[i + 1][w + item_weight]
                else dp[i + 1][w + item_weight]
            )
            weight.add(w + item_weight)
print((max(dp[N])))

import sys

readline = sys.stdin.readline
N, W = list(map(int, readline().split()))
dp = [0] * (W + 1)
weights = {0}
add = weights.add
for i in range(N):
    item_v, item_w = list(map(int, readline().split()))
    for w in sorted(weights, reverse=True):
        if w + item_w <= W and dp[w + item_w] < dp[w] + item_v:
            dp[w + item_w] = dp[w] + item_v
            add(w + item_w)
print((max(dp)))

-a = [(v, w) for _ in [None] * N for v, w in (list(map(int, readline().split())),)] -dp = [[0] * (W + 1) for _ in [None] * (N + 1)] -dp[0][0] = 0 -weight = {0} +dp = [0] * (W + 1) +weights = {0} +add = weights.add -    item_value, item_weight = a[i] -    for w in weight.copy(): -        dp[i + 1][w] = dp[i + 1][w] if dp[i + 1][w] > dp[i][w] else dp[i][w] -        nvalue = dp[i][w] + item_value -        if w + item_weight <= W: -            dp[i + 1][w + item_weight] = ( -                nvalue -                if nvalue > dp[i + 1][w + item_weight] -                else dp[i + 1][w + item_weight] -            ) -            weight.add(w + item_weight) -print((max(dp[N]))) +    item_v, item_w = list(map(int, readline().split())) +    for w in sorted(weights, reverse=True): +        if w + item_w <= W and dp[w + item_w] < dp[w] + item_v: +            dp[w + item_w] = dp[w] + item_v +            add(w + item_w) +print((max(dp)))