# Educational DP Contest D-knapsack



def knapsack(N, W, wv):

    # initialize

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

    

    # DP

    for i in range(N):

        for j in range(W+1):

            if j >= wv[i][0]:

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

            else:

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

    return dp[N][W]



if __name__ == "__main__":

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

    wv = []

    for _ in range(N):

        wv.append(list(map(int, input().split())))

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

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



dp = []

for _ in range(N+1):

    dp.append([0] * (W+1))



for i in range(N):

    for j in range(W+1):

        if j >= wv[i][0]:

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

        else:

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

print((dp[N][W]))
# Educational DP Contest D-knapsack
def knapsack(N, W, wv):
    # initialize
    dp = [list(0 for _ in range(W + 1)) for j in range(N + 1)]
    # DP
    for i in range(N):
        for j in range(W + 1):
            if j >= wv[i][0]:
                dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i][0]] + wv[i][1])
            else:
                dp[i + 1][j] = dp[i][j]
    return dp[N][W]


if __name__ == "__main__":
    N, W = list(map(int, input().split()))
    wv = []
    for _ in range(N):
        wv.append(list(map(int, input().split())))
    print((knapsack(N, W, wv)))

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

-# Educational DP Contest D-knapsack -def knapsack(N, W, wv): -    # initialize -    dp = [list(0 for _ in range(W + 1)) for j in range(N + 1)] -    # DP -    for i in range(N): -        for j in range(W + 1): -            if j >= wv[i][0]: -                dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i][0]] + wv[i][1]) -            else: -                dp[i + 1][j] = dp[i][j] -    return dp[N][W] - - -if __name__ == "__main__": -    N, W = list(map(int, input().split())) -    wv = [] -    for _ in range(N): -        wv.append(list(map(int, input().split()))) -    print((knapsack(N, W, wv))) +N, W = list(map(int, input().split())) +wv = [list(map(int, input().split())) for _ in range(N)] +dp = [] +for _ in range(N + 1): +    dp.append([0] * (W + 1)) +for i in range(N): +    for j in range(W + 1): +        if j >= wv[i][0]: +            dp[i + 1][j] = max(dp[i][j], dp[i][j - wv[i][0]] + wv[i][1]) +        else: +            dp[i + 1][j] = dp[i][j] +print((dp[N][W]))