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

Bs = []

for i in range(N):

    Bs.append(tuple(map(int, input().split())))



dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]

for i in range(N - 1, -1, -1):

    for j in range(W + 1):

        dp[i][j] = max(dp[i + 1][j], (dp[i + 1][j - Bs[i][0]] + Bs[i][1]) if j >= Bs[i][0] else 0)



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

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



dp = [0] * (W + 1)

for w, v in Bs:

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

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



print((dp[W]))

N, W = list(map(int, input().split()))
Bs = []
for i in range(N):
    Bs.append(tuple(map(int, input().split())))
dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
for i in range(N - 1, -1, -1):
    for j in range(W + 1):
        dp[i][j] = max(
            dp[i + 1][j], (dp[i + 1][j - Bs[i][0]] + Bs[i][1]) if j >= Bs[i][0] else 0
        )
print((dp[0][W]))

N, W = list(map(int, input().split()))
Bs = [tuple(map(int, input().split())) for _ in range(N)]
dp = [0] * (W + 1)
for w, v in Bs:
    for i in range(W, w - 1, -1):
        dp[i] = max(dp[i], dp[i - w] + v)
print((dp[W]))

-Bs = [] -for i in range(N): -    Bs.append(tuple(map(int, input().split()))) -dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)] -for i in range(N - 1, -1, -1): -    for j in range(W + 1): -        dp[i][j] = max( -            dp[i + 1][j], (dp[i + 1][j - Bs[i][0]] + Bs[i][1]) if j >= Bs[i][0] else 0 -        ) -print((dp[0][W])) +Bs = [tuple(map(int, input().split())) for _ in range(N)] +dp = [0] * (W + 1) +for w, v in Bs: +    for i in range(W, w - 1, -1): +        dp[i] = max(dp[i], dp[i - w] + v) +print((dp[W]))