n,k = [int(i) for i in input().split()]

w = []

v = []

for _ in range(n):

    a,b = [int(i) for i in input().split()]

    w.append(a)

    v.append(b)



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



for i in range(n):

    for j in range(k+1):

        if j >= w[i]:

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

        else:

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

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

import numpy as np

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



items = list(list(map(int, input().split())) for _ in [0]*n)

dp = np.zeros(w+1, dtype='int64')



for weight, value in items:

    dp[weight:] = np.maximum(dp[weight:], dp[:w-weight+1] + value)

print((dp.max()))

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

import numpy as np

n, w = list(map(int, input().split()))
items = list(list(map(int, input().split())) for _ in [0] * n)
dp = np.zeros(w + 1, dtype="int64")
for weight, value in items:
    dp[weight:] = np.maximum(dp[weight:], dp[: w - weight + 1] + value)
print((dp.max()))

-n, k = [int(i) for i in input().split()] -w = [] -v = [] -for _ in range(n): -    a, b = [int(i) for i in input().split()] -    w.append(a) -    v.append(b) -dp = [[0 for _ in range(k + 1)] for _ in range(n + 1)] -for i in range(n): -    for j in range(k + 1): -        if j >= w[i]: -            dp[i + 1][j] = max(dp[i][j - w[i]] + v[i], dp[i][j]) -        else: -            dp[i + 1][j] = dp[i][j] -print((dp[-1][-1])) +import numpy as np + +n, w = list(map(int, input().split())) +items = list(list(map(int, input().split())) for _ in [0] * n) +dp = np.zeros(w + 1, dtype="int64") +for weight, value in items: +    dp[weight:] = np.maximum(dp[weight:], dp[: w - weight + 1] + value) +print((dp.max()))