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

w = []

v = []

for i in range(n):

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

    w.append(a)

    v.append(b)



c = [[0 for j in range(W)] for i in range(n)]

for i in range(W):

    if i+1 < w[0]:

        c[0][i] = 0

    else:

        c[0][i] = v[0]



for i in range(1,n):

    for j in range(W):

        if j+1 < w[i]:

            c[i][j] = c[i-1][j]

        else:

            diff = (j+1)-w[i]

            if diff > 0:

                c[i][j] = max(c[i-1][j], v[i]+c[i-1][diff-1])

            else:

                c[i][j] = max(c[i-1][j], v[i])

print((max(c[-1])))

def knapsack(W,weight,value):

    n = len(weight)#or len(value)

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

    # 初期化

    for j in range(W):

        dp[0][j] = 0

    for i in range(n):

        for j in range(W+1):

            if weight[i] <= j:

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

            else:

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

    return dp



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

values, weights = [],[]

for _ in range(N):

    ｗ,ｖ = list(map(int,input().split()))

    values.append(v)

    weights.append(w)

    

dp = knapsack(W,weights,values)

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

def knapsack(W, weight, value):
    n = len(weight)  # or len(value)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    # 初期化
    for j in range(W):
        dp[0][j] = 0
    for i in range(n):
        for j in range(W + 1):
            if weight[i] <= j:
                dp[i + 1][j] = max(dp[i][j - weight[i]] + value[i], dp[i][j])
            else:
                dp[i + 1][j] = dp[i][j]
    return dp


N, W = list(map(int, input().split()))
values, weights = [], []
for _ in range(N):
    ｗ, ｖ = list(map(int, input().split()))
    values.append(v)
    weights.append(w)
dp = knapsack(W, weights, values)
print((dp[-1][-1]))

-n, W = list(map(int, input().split())) -w = [] -v = [] -for i in range(n): -    a, b = list(map(int, input().split())) -    w.append(a) -    v.append(b) -c = [[0 for j in range(W)] for i in range(n)] -for i in range(W): -    if i + 1 < w[0]: -        c[0][i] = 0 -    else: -        c[0][i] = v[0] -for i in range(1, n): +def knapsack(W, weight, value): +    n = len(weight)  # or len(value) +    dp = [[0] * (W + 1) for _ in range(n + 1)] +    # 初期化 -        if j + 1 < w[i]: -            c[i][j] = c[i - 1][j] -        else: -            diff = (j + 1) - w[i] -            if diff > 0: -                c[i][j] = max(c[i - 1][j], v[i] + c[i - 1][diff - 1]) +        dp[0][j] = 0 +    for i in range(n): +        for j in range(W + 1): +            if weight[i] <= j: +                dp[i + 1][j] = max(dp[i][j - weight[i]] + value[i], dp[i][j]) -                c[i][j] = max(c[i - 1][j], v[i]) -print((max(c[-1]))) +                dp[i + 1][j] = dp[i][j] +    return dp + + +N, W = list(map(int, input().split())) +values, weights = [], [] +for _ in range(N): +    ｗ, ｖ = list(map(int, input().split())) +    values.append(v) +    weights.append(w) +dp = knapsack(W, weights, values) +print((dp[-1][-1]))