import sys



stdin = sys.stdin



ni = lambda: int(ns())

na = lambda: list(map(int, stdin.readline().split()))

ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces



n, W = na()

w = []

v = []

for i in range(n):

    x,y = list(map(int,input().split()))

    w.append(x)

    v.append(y)



dp = [[0]*(W+1) for i in range(n+1)]



for i in range(n):

      for j in range(W+1):

        if j < w[i]:

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

        else:

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



print((dp[n][W]))

      
import sys

input = sys.stdin.readline

n,w = list(map(int,input().split()))

wv = [tuple(map(int,input().split())) for i in range(n)]



dp = [0]*(w+1)

for i in range(n):

    for j in range(w,wv[i][0]-1,-1):

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



print((max(dp)))
import sys

stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces
n, W = na()
w = []
v = []
for i in range(n):
    x, y = list(map(int, input().split()))
    w.append(x)
    v.append(y)
dp = [[0] * (W + 1) for i in range(n + 1)]
for i in range(n):
    for j in range(W + 1):
        if j < w[i]:
            dp[i + 1][j] = dp[i][j]
        else:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
print((dp[n][W]))

import sys

input = sys.stdin.readline
n, w = list(map(int, input().split()))
wv = [tuple(map(int, input().split())) for i in range(n)]
dp = [0] * (w + 1)
for i in range(n):
    for j in range(w, wv[i][0] - 1, -1):
        dp[j] = max(dp[j], dp[j - wv[i][0]] + wv[i][1])
print((max(dp)))

-stdin = sys.stdin -ni = lambda: int(ns()) -na = lambda: list(map(int, stdin.readline().split())) -ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces -n, W = na() -w = [] -v = [] +input = sys.stdin.readline +n, w = list(map(int, input().split())) +wv = [tuple(map(int, input().split())) for i in range(n)] +dp = [0] * (w + 1) -    x, y = list(map(int, input().split())) -    w.append(x) -    v.append(y) -dp = [[0] * (W + 1) for i in range(n + 1)] -for i in range(n): -    for j in range(W + 1): -        if j < w[i]: -            dp[i + 1][j] = dp[i][j] -        else: -            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i]) -print((dp[n][W])) +    for j in range(w, wv[i][0] - 1, -1): +        dp[j] = max(dp[j], dp[j - wv[i][0]] + wv[i][1]) +print((max(dp)))