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

    w,v = wv[i]

    if j-w>=0:

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

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

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

import numpy as np,sys

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

N,W = LI()

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

dp = np.zeros(W+1,dtype=int) #1_indexed

for i in range(N):

    w,v = wv[i]

    dp[w:] = np.fmax(dp[:-w]+v,dp[w:])

print((dp[-1]))

import 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(N)), list(range(W + 1))):
    w, v = wv[i]
    if j - w >= 0:
        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w] + v)
    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])
print((dp[-1][-1]))

import numpy as np, sys


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


N, W = LI()
wv = [LI() for _ in range(N)]
dp = np.zeros(W + 1, dtype=int)  # 1_indexed
for i in range(N):
    w, v = wv[i]
    dp[w:] = np.fmax(dp[:-w] + v, dp[w:])
print((dp[-1]))

-import itertools, sys +import numpy as np, sys -dp = [[0] * (W + 1) for _ in range(N + 1)]  # 1_indexed -for i, j in itertools.product(list(range(N)), list(range(W + 1))): +dp = np.zeros(W + 1, dtype=int)  # 1_indexed +for i in range(N): -    if j - w >= 0: -        dp[i + 1][j] = max(dp[i + 1][j], dp[i][j - w] + v) -    dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]) -print((dp[-1][-1])) +    dp[w:] = np.fmax(dp[:-w] + v, dp[w:]) +print((dp[-1]))