import numpy as np

INF = 2**60 # 無限大を表す値

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

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

dp = np.full((N+1, W+1), -INF, dtype = np.int64)

dp[0][0] = 0 # 初期条件

for i, (w, v) in enumerate(wv):

    dp[i+1] = np.maximum(dp[i+1], dp[i])

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

print((np.max(dp[N][:W+1])))
import numpy as np

INF = 2**60 # 無限大を表す値

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

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

dp = np.full((N+1, W+1), -INF, dtype = np.int64)

dp[0][0] = 0 # 初期条件

for i, (w, v) in enumerate(wv):

    dp[i+1] = np.maximum(dp[i+1], dp[i])

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

print((np.max(dp[N][:W+1])))
import numpy as np

INF = 2**60  # 無限大を表す値
N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for i in range(N)]
dp = np.full((N + 1, W + 1), -INF, dtype=np.int64)
dp[0][0] = 0  # 初期条件
for i, (w, v) in enumerate(wv):
    dp[i + 1] = np.maximum(dp[i + 1], dp[i])
    dp[i + 1][w:] = np.maximum(dp[i + 1][w:], dp[i][:-w] + v)
print((np.max(dp[N][: W + 1])))

import numpy as np

INF = 2**60  # 無限大を表す値
N, W = list(map(int, input().split()))
wv = [tuple(map(int, input().split())) for i in range(N)]
dp = np.full((N + 1, W + 1), -INF, dtype=np.int64)
dp[0][0] = 0  # 初期条件
for i, (w, v) in enumerate(wv):
    dp[i + 1] = np.maximum(dp[i + 1], dp[i])
    dp[i + 1][w:] = np.maximum(dp[i + 1][w:], dp[i][:-w] + v)
print((np.max(dp[N][: W + 1])))

-wv = [list(map(int, input().split())) for i in range(N)] +wv = [tuple(map(int, input().split())) for i in range(N)]