import math



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

weights = []

costs = []

for i in range(n):

    a,b = list(map(int, input().split()))

    weights.append(a)

    costs.append(b)

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

for i in range(w+1):

    if(i>= weights[0]):

        dp[0][i] = costs[0]



for i in range(1, n):

    for j in range(w+1):

        if(j >= weights[i]):

            val = max(dp[i-1][j], costs[i]+dp[i-1][j-weights[i]])

            dp[i][j] = val

        else:

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

print((dp[-1][-1]))
import math



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

dp = [0]*(W+1)

for i in range(n):

    weight, cost = list(map(int, input().split()))

    for weight_already in range(W-weight, -1, -1):

        dp[weight_already+weight] = max(dp[weight_already+weight], dp[weight_already]+cost)

ans = max(dp)

print(ans)
import math

n, w = list(map(int, input().split()))
weights = []
costs = []
for i in range(n):
    a, b = list(map(int, input().split()))
    weights.append(a)
    costs.append(b)
dp = [[0 for i in range(w + 1)] for i in range(n)]
for i in range(w + 1):
    if i >= weights[0]:
        dp[0][i] = costs[0]
for i in range(1, n):
    for j in range(w + 1):
        if j >= weights[i]:
            val = max(dp[i - 1][j], costs[i] + dp[i - 1][j - weights[i]])
            dp[i][j] = val
        else:
            dp[i][j] = max(dp[i][j], dp[i - 1][j])
print((dp[-1][-1]))

import math

n, W = list(map(int, input().split()))
dp = [0] * (W + 1)
for i in range(n):
    weight, cost = list(map(int, input().split()))
    for weight_already in range(W - weight, -1, -1):
        dp[weight_already + weight] = max(
            dp[weight_already + weight], dp[weight_already] + cost
        )
ans = max(dp)
print(ans)

-n, w = list(map(int, input().split())) -weights = [] -costs = [] +n, W = list(map(int, input().split())) +dp = [0] * (W + 1) -    a, b = list(map(int, input().split())) -    weights.append(a) -    costs.append(b) -dp = [[0 for i in range(w + 1)] for i in range(n)] -for i in range(w + 1): -    if i >= weights[0]: -        dp[0][i] = costs[0] -for i in range(1, n): -    for j in range(w + 1): -        if j >= weights[i]: -            val = max(dp[i - 1][j], costs[i] + dp[i - 1][j - weights[i]]) -            dp[i][j] = val -        else: -            dp[i][j] = max(dp[i][j], dp[i - 1][j]) -print((dp[-1][-1])) +    weight, cost = list(map(int, input().split())) +    for weight_already in range(W - weight, -1, -1): +        dp[weight_already + weight] = max( +            dp[weight_already + weight], dp[weight_already] + cost +        ) +ans = max(dp) +print(ans)