import sys

import numpy as np

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

it = iter(map(int, sys.stdin.read().split()))

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

for w, v in zip(it, it):

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

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

import numpy as np

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

it = iter(map(int, sys.stdin.read().split()))

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

for w, v in zip(it, it):

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

print((dp[-1]))
import sys
import numpy as np

N, W = list(map(int, input().split()))
it = iter(map(int, sys.stdin.read().split()))
dp = np.zeros(W + 1, dtype=int)
for w, v in zip(it, it):
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
print((dp[-1]))

import sys
import numpy as np

N, W = list(map(int, input().split()))
it = iter(map(int, sys.stdin.read().split()))
dp = np.zeros(W + 1, dtype=np.int64)
for w, v in zip(it, it):
    np.maximum(dp[:-w] + v, dp[w:], out=dp[w:])
print((dp[-1]))

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