import collections,sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

N,W = LI()

wv = [LI() for _ in range(N)]

dp = [collections.defaultdict(int) for _ in range(N+1)] #1_indexed

dp[0][0] = 0

for i in range(1,N+1):

    w,v = wv[i-1]

    for dw,dv in list(dp[i-1].items()):

        dp[i][dw] = max(dp[i][dw],dv)

        if dw+w<=W:

            dp[i][dw+w] = max(dp[i][dw+w],dv+v)

print((max(dp[-1].values())))

import collections,itertools,sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

N,W = LI()

wv = [LI() for _ in range(N)]

dp = [[0]*(W+1) for _ in range(N+1)] #1_indexed

for i,j in itertools.product(list(range(1,N+1)),list(range(W+1))):

    w,v = wv[i-1]

    if j-w>=0:

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

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

print((dp[-1][-1]))

import collections, sys


def LI():
    return list(map(int, sys.stdin.readline().rstrip().split()))


N, W = LI()
wv = [LI() for _ in range(N)]
dp = [collections.defaultdict(int) for _ in range(N + 1)]  # 1_indexed
dp[0][0] = 0
for i in range(1, N + 1):
    w, v = wv[i - 1]
    for dw, dv in list(dp[i - 1].items()):
        dp[i][dw] = max(dp[i][dw], dv)
        if dw + w <= W:
            dp[i][dw + w] = max(dp[i][dw + w], dv + v)
print((max(dp[-1].values())))

import collections, itertools, sys


def LI():
    return list(map(int, sys.stdin.readline().rstrip().split()))


N, W = LI()
wv = [LI() for _ in range(N)]
dp = [[0] * (W + 1) for _ in range(N + 1)]  # 1_indexed
for i, j in itertools.product(list(range(1, N + 1)), list(range(W + 1))):
    w, v = wv[i - 1]
    if j - w >= 0:
        dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + v)
    dp[i][j] = max(dp[i][j], dp[i - 1][j])
print((dp[-1][-1]))

-import collections, sys +import collections, itertools, sys -dp = [collections.defaultdict(int) for _ in range(N + 1)]  # 1_indexed -dp[0][0] = 0 -for i in range(1, N + 1): +dp = [[0] * (W + 1) for _ in range(N + 1)]  # 1_indexed +for i, j in itertools.product(list(range(1, N + 1)), list(range(W + 1))): -    for dw, dv in list(dp[i - 1].items()): -        dp[i][dw] = max(dp[i][dw], dv) -        if dw + w <= W: -            dp[i][dw + w] = max(dp[i][dw + w], dv + v) -print((max(dp[-1].values()))) +    if j - w >= 0: +        dp[i][j] = max(dp[i][j], dp[i - 1][j - w] + v) +    dp[i][j] = max(dp[i][j], dp[i - 1][j]) +print((dp[-1][-1]))