def dp():

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

  WV = (list(map(int, input().split())) for _ in range(N))



  DP = [0] * (W+1)

  for w, v in WV:

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

      dp = DP[j-w] + v 

      if DP[j] < dp:

        DP[j] = dp

  return max(DP)

print((dp()))

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



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



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



for i in range(N):

  w, v = wv[i]

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

    if j - w < 0:

      dp[i][j] = dp[i-1][j]

    else:

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



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

def dp():
    N, W = list(map(int, input().split()))
    WV = (list(map(int, input().split())) for _ in range(N))
    DP = [0] * (W + 1)
    for w, v in WV:
        for j in range(W, w - 1, -1):
            dp = DP[j - w] + v
            if DP[j] < dp:
                DP[j] = dp
    return max(DP)


print((dp()))

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

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