# 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 _ in range(N + 1)]

dp[0][0] = 0



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

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

        if w == 0:

            dp[n][0] = 0

            continue

        if w < s[n - 1][0]:

            dp[n][w] = dp[n - 1][w]

        else:

            dp[n][w] = max(dp[n - 1][w],

                           dp[n - 1][w - s[n - 1][0]] + s[n - 1][1])



print((dp[N][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],

                             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 _ in range(N + 1)]
dp[0][0] = 0
for n in range(1, N + 1):
    for w in range(0, W + 1):
        if w == 0:
            dp[n][0] = 0
            continue
        if w < s[n - 1][0]:
            dp[n][w] = dp[n - 1][w]
        else:
            dp[n][w] = max(dp[n - 1][w], dp[n - 1][w - s[n - 1][0]] + s[n - 1][1])
print((dp[N][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], dp[w - s[n - 1][0]] + s[n - 1][1])
    dp = next_dp[:]
print((dp[W]))

-dp = [[0] * (W + 1) for _ in range(N + 1)] -dp[0][0] = 0 +dp = [0] * (W + 1) +next_dp = [0] * (W + 1) -        if w == 0: -            dp[n][0] = 0 -            continue -        if w < s[n - 1][0]: -            dp[n][w] = dp[n - 1][w] -        else: -            dp[n][w] = max(dp[n - 1][w], dp[n - 1][w - s[n - 1][0]] + s[n - 1][1]) -print((dp[N][W])) +        if w >= s[n - 1][0]: +            next_dp[w] = max(next_dp[w], dp[w], dp[w - s[n - 1][0]] + s[n - 1][1]) +    dp = next_dp[:] +print((dp[W]))