# using dp with memoization, TLE

from sys import stdin

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

m = stdin.read().splitlines()

s = [[int(i) for i in line.split()] for line in m]



dp = [0] * (W + 1)

next_dp = [0] * (W + 1)

for n in range(1, N + 1):

    for w in range(0, W + 1):

        if w >= s[n - 1][0]:

            next_dp[w] = max(next_dp[w], dp[w - s[n - 1][0]] + s[n - 1][1])

    dp = next_dp[:]

print((dp[W]))

# using dp with memoization, TLE

from sys import stdin

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

m = stdin.read().splitlines()

s = [[int(i) for i in line.split()] for line in m]



dp = [0] * (W + 1)



for n in range(1, N + 1):

    w0, v0 = s[n - 1]

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



        dp[w] = max(dp[w], dp[w - w0] + v0)



print((dp[W]))

# using dp with memoization, TLE
from sys import stdin

N, W = list(map(int, input().split()))
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]
dp = [0] * (W + 1)
next_dp = [0] * (W + 1)
for n in range(1, N + 1):
    for w in range(0, W + 1):
        if w >= s[n - 1][0]:
            next_dp[w] = max(next_dp[w], dp[w - s[n - 1][0]] + s[n - 1][1])
    dp = next_dp[:]
print((dp[W]))

# using dp with memoization, TLE
from sys import stdin

N, W = list(map(int, input().split()))
m = stdin.read().splitlines()
s = [[int(i) for i in line.split()] for line in m]
dp = [0] * (W + 1)
for n in range(1, N + 1):
    w0, v0 = s[n - 1]
    for w in range(W, w0 - 1, -1):
        dp[w] = max(dp[w], dp[w - w0] + v0)
print((dp[W]))

-next_dp = [0] * (W + 1) -    for w in range(0, W + 1): -        if w >= s[n - 1][0]: -            next_dp[w] = max(next_dp[w], dp[w - s[n - 1][0]] + s[n - 1][1]) -    dp = next_dp[:] +    w0, v0 = s[n - 1] +    for w in range(W, w0 - 1, -1): +        dp[w] = max(dp[w], dp[w - w0] + v0)