# TODO:実装

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



DP = {0: 0}

for i in range(N):

    wi, vi = list(map(int, input().split()))

    DP_dst = DP.copy()

    for j in DP:

        if j+wi <= W:

            DP_dst[j+wi] = max(DP.get(j+wi, 0), DP[j]+vi)

    DP = DP_dst

print((max((DP[x] for x in DP))))

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



DP = {0: 0}

for i in range(N):

    wi, vi = list(map(int, input().split()))

    p = {}

    for j in DP:

        if j+wi <= W and DP.get(j+wi, 0) < DP[j]+vi:

            p[j+wi] = DP[j]+vi

    for pi in p:

        DP[pi] = p[pi]

print((max((DP[x] for x in DP))))

# TODO:実装
N, W = list(map(int, input().split()))
DP = {0: 0}
for i in range(N):
    wi, vi = list(map(int, input().split()))
    DP_dst = DP.copy()
    for j in DP:
        if j + wi <= W:
            DP_dst[j + wi] = max(DP.get(j + wi, 0), DP[j] + vi)
    DP = DP_dst
print((max((DP[x] for x in DP))))

N, W = list(map(int, input().split()))
DP = {0: 0}
for i in range(N):
    wi, vi = list(map(int, input().split()))
    p = {}
    for j in DP:
        if j + wi <= W and DP.get(j + wi, 0) < DP[j] + vi:
            p[j + wi] = DP[j] + vi
    for pi in p:
        DP[pi] = p[pi]
print((max((DP[x] for x in DP))))

-# TODO:実装 -    DP_dst = DP.copy() +    p = {} -        if j + wi <= W: -            DP_dst[j + wi] = max(DP.get(j + wi, 0), DP[j] + vi) -    DP = DP_dst +        if j + wi <= W and DP.get(j + wi, 0) < DP[j] + vi: +            p[j + wi] = DP[j] + vi +    for pi in p: +        DP[pi] = p[pi]