import numpy as np

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

l = sorted([tuple(map(int, input().split())) for i in range(N)], key=lambda x: x[0])

dp = np.zeros(W+1, dtype=int)

for i in range(N):

    w = l[i][0]

    dp[w:] = np.maximum(dp[w:], dp[:-w] + l[i][1])

print((dp[-1]))
N, W = list(map(int, input().split()))

wv = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: x[0])



# 重さをi、dp[i]を価値の最大値とする

dp = [0]*(W+1)

dp[0] = 0



for i in range(N):

    w, v = wv[i]

    # 前から埋めていくとさっき更新したやつをもとに更新してしまう（同じものを使ってしまう）ので逆から更新する

    for j in range(W, w-1, -1):

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



print((dp[W]))
import numpy as np

N, W = list(map(int, input().split()))
l = sorted([tuple(map(int, input().split())) for i in range(N)], key=lambda x: x[0])
dp = np.zeros(W + 1, dtype=int)
for i in range(N):
    w = l[i][0]
    dp[w:] = np.maximum(dp[w:], dp[:-w] + l[i][1])
print((dp[-1]))

N, W = list(map(int, input().split()))
wv = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: x[0])
# 重さをi、dp[i]を価値の最大値とする
dp = [0] * (W + 1)
dp[0] = 0
for i in range(N):
    w, v = wv[i]
    # 前から埋めていくとさっき更新したやつをもとに更新してしまう（同じものを使ってしまう）ので逆から更新する
    for j in range(W, w - 1, -1):
        dp[j] = max(dp[j], dp[j - w] + v)
print((dp[W]))

-import numpy as np - -l = sorted([tuple(map(int, input().split())) for i in range(N)], key=lambda x: x[0]) -dp = np.zeros(W + 1, dtype=int) +wv = sorted([list(map(int, input().split())) for i in range(N)], key=lambda x: x[0]) +# 重さをi、dp[i]を価値の最大値とする +dp = [0] * (W + 1) +dp[0] = 0 -    w = l[i][0] -    dp[w:] = np.maximum(dp[w:], dp[:-w] + l[i][1]) -print((dp[-1])) +    w, v = wv[i] +    # 前から埋めていくとさっき更新したやつをもとに更新してしまう（同じものを使ってしまう）ので逆から更新する +    for j in range(W, w - 1, -1): +        dp[j] = max(dp[j], dp[j - w] + v) +print((dp[W]))