import sys 

read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines



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

w=[];v=[]

for _ in range(N):

  a,b = list(map(int, readline().split()))

  w.append(a)

  v.append(b)

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

for i in range(N):

  for j in range(W+1):

    if j >= w[i]:

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

    else:

      dp[i+1][j] = dp[i][j]

print((dp[N][W]))
import sys

import numpy as np

read = sys.stdin.buffer.read

readline = sys.stdin.buffer.readline

readlines = sys.stdin.buffer.readlines

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

WV = [list(map(int,readline().split())) for _ in range(N)]



dp = np.zeros(W+1,np.int64)

for w,v in WV:

  np.maximum(dp[w:],dp[:-w].copy() +v,out=dp[w:])

print((dp.max()))
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, W = list(map(int, readline().split()))
w = []
v = []
for _ in range(N):
    a, b = list(map(int, readline().split()))
    w.append(a)
    v.append(b)
dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
for i in range(N):
    for j in range(W + 1):
        if j >= w[i]:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
        else:
            dp[i + 1][j] = dp[i][j]
print((dp[N][W]))

import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, W = list(map(int, readline().split()))
WV = [list(map(int, readline().split())) for _ in range(N)]
dp = np.zeros(W + 1, np.int64)
for w, v in WV:
    np.maximum(dp[w:], dp[:-w].copy() + v, out=dp[w:])
print((dp.max()))

+import numpy as np -w = [] -v = [] -for _ in range(N): -    a, b = list(map(int, readline().split())) -    w.append(a) -    v.append(b) -dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)] -for i in range(N): -    for j in range(W + 1): -        if j >= w[i]: -            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]) -        else: -            dp[i + 1][j] = dp[i][j] -print((dp[N][W])) +WV = [list(map(int, readline().split())) for _ in range(N)] +dp = np.zeros(W + 1, np.int64) +for w, v in WV: +    np.maximum(dp[w:], dp[:-w].copy() + v, out=dp[w:]) +print((dp.max()))