import sys

input=sys.stdin.readline



def f(n,W):

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

    dp = [-1] * (W + 1)

    dp[0] = 0

    for w, v in wv:

        for i in range(W - w, -1, -1):

            if dp[i] == -1: continue

            nv = dp[i] + v

            if nv > dp[i + w]:

                dp[i + w] = nv

    print((max(dp)))



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

f(n,W)

import numpy as np

import sys

input=sys.stdin.readline



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

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

dp=np.zeros(W+1,dtype="i8")

for w,v in wv:

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

print((dp[-1]))

import sys

input = sys.stdin.readline


def f(n, W):
    wv = [list(map(int, input().split())) for _ in range(n)]
    dp = [-1] * (W + 1)
    dp[0] = 0
    for w, v in wv:
        for i in range(W - w, -1, -1):
            if dp[i] == -1:
                continue
            nv = dp[i] + v
            if nv > dp[i + w]:
                dp[i + w] = nv
    print((max(dp)))


n, W = list(map(int, input().split()))
f(n, W)

import numpy as np
import sys

input = sys.stdin.readline
n, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(n)]
dp = np.zeros(W + 1, dtype="i8")
for w, v in wv:
    np.maximum(dp[w:], dp[: W + 1 - w] + v, out=dp[w:])
print((dp[-1]))

+import numpy as np - - -def f(n, W): -    wv = [list(map(int, input().split())) for _ in range(n)] -    dp = [-1] * (W + 1) -    dp[0] = 0 -    for w, v in wv: -        for i in range(W - w, -1, -1): -            if dp[i] == -1: -                continue -            nv = dp[i] + v -            if nv > dp[i + w]: -                dp[i + w] = nv -    print((max(dp))) - - -f(n, W) +wv = [list(map(int, input().split())) for _ in range(n)] +dp = np.zeros(W + 1, dtype="i8") +for w, v in wv: +    np.maximum(dp[w:], dp[: W + 1 - w] + v, out=dp[w:]) +print((dp[-1]))