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 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 in range(1,N+1):

    w,v = wv[i-1]

    for j in range(W+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, 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 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 in range(1, N + 1):
    w, v = wv[i - 1]
    for j in range(W + 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, itertools, sys +import sys -for i, j in itertools.product(list(range(1, N + 1)), list(range(W + 1))): +for i in range(1, N + 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]) +    for j in range(W + 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])