def calc():

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

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

  dp[0]=0

  for i in range(N):

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

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

      if dp[j]!=-1:

        if dp[j+w]<dp[j]+v:

          dp[j+w]=dp[j]+v

  print((max(dp)))

  

calc()
N,W=list(map(int,input().split()))

weight=[0]*N

values=[0]*N

for i in range(N):

  weight[i],values[i]=list(map(int,input().split()))



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



for i in range(N):

  for w in range(W+1):

    if w>=weight[i]:

      dp[i+1][w]=max(dp[i][w],dp[i][w-weight[i]]+values[i])

    else:

      dp[i+1][w]=dp[i][w]

      

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

def calc():
    N, W = list(map(int, input().split()))
    dp = [-1] * (W + 1)
    dp[0] = 0
    for i in range(N):
        w, v = list(map(int, input().split()))
        for j in range(W - w, -1, -1):
            if dp[j] != -1:
                if dp[j + w] < dp[j] + v:
                    dp[j + w] = dp[j] + v
    print((max(dp)))


calc()

N, W = list(map(int, input().split()))
weight = [0] * N
values = [0] * N
for i in range(N):
    weight[i], values[i] = list(map(int, input().split()))
dp = [[0 for i in range(W + 1)] for j in range(N + 1)]
for i in range(N):
    for w in range(W + 1):
        if w >= weight[i]:
            dp[i + 1][w] = max(dp[i][w], dp[i][w - weight[i]] + values[i])
        else:
            dp[i + 1][w] = dp[i][w]
print((dp[N][W]))

-def calc(): -    N, W = list(map(int, input().split())) -    dp = [-1] * (W + 1) -    dp[0] = 0 -    for i in range(N): -        w, v = list(map(int, input().split())) -        for j in range(W - w, -1, -1): -            if dp[j] != -1: -                if dp[j + w] < dp[j] + v: -                    dp[j + w] = dp[j] + v -    print((max(dp))) - - -calc() +N, W = list(map(int, input().split())) +weight = [0] * N +values = [0] * N +for i in range(N): +    weight[i], values[i] = list(map(int, input().split())) +dp = [[0 for i in range(W + 1)] for j in range(N + 1)] +for i in range(N): +    for w in range(W + 1): +        if w >= weight[i]: +            dp[i + 1][w] = max(dp[i][w], dp[i][w - weight[i]] + values[i]) +        else: +            dp[i + 1][w] = dp[i][w] +print((dp[N][W]))