#EDP-D, E

import sys

from collections import defaultdict

n, W = list(map(int, sys.stdin.readline().split()))

dp = [defaultdict(int) for _ in range(n)]

#初期設定

w, v = list(map(int, sys.stdin.readline().split()))

dp[0][w] = v

#print(dp)



for i in range(1, n):

    w, v = list(map(int, sys.stdin.readline().split()))

    dp[i][w] = max(dp[i-1].get(w, 0), v)

    for w1, v1 in list(dp[i-1].items()):

        dp[i][w1] = max(dp[i][w1], v1)

        if w+w1<=W:

            dp[i][w1+w] = max(dp[i][w1+w], v1+v)



print((max(dp[-1].values())))
#DP D

def main():

    import sys

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

    L = tuple([tuple(map(int, sys.stdin.readline().split())) for _ in range(N)])

    #print(L)

    dp = [[0 for i in range(10**5+1)] for _ in range(N)]

    for i in range(N):

        w, v = L[i][0], L[i][1]

        if i>=1:

            dp[i][w] = max(v, dp[i-1][w])

        elif i==0:

            dp[i][w] = v

        for j in range(10**5+1):

            if i>=1 and dp[i-1][j]!=0:

                dp[i][j] = max(dp[i-1][j], dp[i][j])

                if w+j <=10**5:

                    dp[i][w+j] = max(dp[i-1][w+j], v + dp[i-1][j])

                

    print((max(dp[-1][:W+1])))







if __name__=='__main__':

    main()
# EDP-D, E
import sys
from collections import defaultdict

n, W = list(map(int, sys.stdin.readline().split()))
dp = [defaultdict(int) for _ in range(n)]
# 初期設定
w, v = list(map(int, sys.stdin.readline().split()))
dp[0][w] = v
# print(dp)
for i in range(1, n):
    w, v = list(map(int, sys.stdin.readline().split()))
    dp[i][w] = max(dp[i - 1].get(w, 0), v)
    for w1, v1 in list(dp[i - 1].items()):
        dp[i][w1] = max(dp[i][w1], v1)
        if w + w1 <= W:
            dp[i][w1 + w] = max(dp[i][w1 + w], v1 + v)
print((max(dp[-1].values())))

# DP D
def main():
    import sys

    N, W = list(map(int, sys.stdin.readline().split()))
    L = tuple([tuple(map(int, sys.stdin.readline().split())) for _ in range(N)])
    # print(L)
    dp = [[0 for i in range(10**5 + 1)] for _ in range(N)]
    for i in range(N):
        w, v = L[i][0], L[i][1]
        if i >= 1:
            dp[i][w] = max(v, dp[i - 1][w])
        elif i == 0:
            dp[i][w] = v
        for j in range(10**5 + 1):
            if i >= 1 and dp[i - 1][j] != 0:
                dp[i][j] = max(dp[i - 1][j], dp[i][j])
                if w + j <= 10**5:
                    dp[i][w + j] = max(dp[i - 1][w + j], v + dp[i - 1][j])
    print((max(dp[-1][: W + 1])))


if __name__ == "__main__":
    main()

-# EDP-D, E -import sys -from collections import defaultdict +# DP D +def main(): +    import sys -n, W = list(map(int, sys.stdin.readline().split())) -dp = [defaultdict(int) for _ in range(n)] -# 初期設定 -w, v = list(map(int, sys.stdin.readline().split())) -dp[0][w] = v -# print(dp) -for i in range(1, n): -    w, v = list(map(int, sys.stdin.readline().split())) -    dp[i][w] = max(dp[i - 1].get(w, 0), v) -    for w1, v1 in list(dp[i - 1].items()): -        dp[i][w1] = max(dp[i][w1], v1) -        if w + w1 <= W: -            dp[i][w1 + w] = max(dp[i][w1 + w], v1 + v) -print((max(dp[-1].values()))) +    N, W = list(map(int, sys.stdin.readline().split())) +    L = tuple([tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]) +    # print(L) +    dp = [[0 for i in range(10**5 + 1)] for _ in range(N)] +    for i in range(N): +        w, v = L[i][0], L[i][1] +        if i >= 1: +            dp[i][w] = max(v, dp[i - 1][w]) +        elif i == 0: +            dp[i][w] = v +        for j in range(10**5 + 1): +            if i >= 1 and dp[i - 1][j] != 0: +                dp[i][j] = max(dp[i - 1][j], dp[i][j]) +                if w + j <= 10**5: +                    dp[i][w + j] = max(dp[i - 1][w + j], v + dp[i - 1][j]) +    print((max(dp[-1][: W + 1]))) + + +if __name__ == "__main__": +    main()