def submit():

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

    dp = [[0] * (w + 1) for _ in range(n + 1)]



    # dp[i][j] = item iまでで重さjの時に実現する最大価値

    for i in range(1, n + 1):

        wi, vi = list(map(int, input().split()))

        for j in range(1, w + 1):

            if 0 <= j - wi <= w:

                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wi] + vi)

            else:

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

    print((max(dp[n])))



submit()    

        


import numpy as np



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

dp = np.full(w + 1, 0, dtype=int)



# dp[w] : wまでitemを取捨選択した際の最大価値



for _ in range(n):

    wi, vi = list(map(int, input().split()))

    dp[wi:] = np.maximum(dp[:-wi] + vi, dp[wi:])

print((dp[-1]))
def submit():
    n, w = list(map(int, input().split()))
    dp = [[0] * (w + 1) for _ in range(n + 1)]
    # dp[i][j] = item iまでで重さjの時に実現する最大価値
    for i in range(1, n + 1):
        wi, vi = list(map(int, input().split()))
        for j in range(1, w + 1):
            if 0 <= j - wi <= w:
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wi] + vi)
            else:
                dp[i][j] = dp[i - 1][j]
    print((max(dp[n])))


submit()

import numpy as np

n, w = list(map(int, input().split()))
dp = np.full(w + 1, 0, dtype=int)
# dp[w] : wまでitemを取捨選択した際の最大価値
for _ in range(n):
    wi, vi = list(map(int, input().split()))
    dp[wi:] = np.maximum(dp[:-wi] + vi, dp[wi:])
print((dp[-1]))

-def submit(): -    n, w = list(map(int, input().split())) -    dp = [[0] * (w + 1) for _ in range(n + 1)] -    # dp[i][j] = item iまでで重さjの時に実現する最大価値 -    for i in range(1, n + 1): -        wi, vi = list(map(int, input().split())) -        for j in range(1, w + 1): -            if 0 <= j - wi <= w: -                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - wi] + vi) -            else: -                dp[i][j] = dp[i - 1][j] -    print((max(dp[n]))) +import numpy as np - -submit() +n, w = list(map(int, input().split())) +dp = np.full(w + 1, 0, dtype=int) +# dp[w] : wまでitemを取捨選択した際の最大価値 +for _ in range(n): +    wi, vi = list(map(int, input().split())) +    dp[wi:] = np.maximum(dp[:-wi] + vi, dp[wi:]) +print((dp[-1]))