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

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



# DP

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

for i in range(N):

    for j in range(W+1):

        if wv[i][0] <= j:

            dp[i+1][j] = max(dp[i][j - wv[i][0]] + wv[i][1], dp[i][j])

        else:

            dp[i+1][j] = dp[i][j]

print((dp[N][W]))
# Knapsack 1

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

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

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

for n in range(N):

    for w in range(W + 1):

        if wv[n][0] <= w:

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

        else:

            dp[n+1][w] = dp[n][w]

print((dp[N][W]))
N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]
# DP
dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)]
for i in range(N):
    for j in range(W + 1):
        if wv[i][0] <= j:
            dp[i + 1][j] = max(dp[i][j - wv[i][0]] + wv[i][1], dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]
print((dp[N][W]))

# Knapsack 1
N, W = list(map(int, input().split()))
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [[0 for i in range(W + 1)] for j in range(N + 1)]
for n in range(N):
    for w in range(W + 1):
        if wv[n][0] <= w:
            dp[n + 1][w] = max(dp[n][w], dp[n][w - wv[n][0]] + wv[n][1])
        else:
            dp[n + 1][w] = dp[n][w]
print((dp[N][W]))

+# Knapsack 1 -# DP -dp = [[0 for _ in range(W + 1)] for _ in range(N + 1)] -for i in range(N): -    for j in range(W + 1): -        if wv[i][0] <= j: -            dp[i + 1][j] = max(dp[i][j - wv[i][0]] + wv[i][1], dp[i][j]) +dp = [[0 for i in range(W + 1)] for j in range(N + 1)] +for n in range(N): +    for w in range(W + 1): +        if wv[n][0] <= w: +            dp[n + 1][w] = max(dp[n][w], dp[n][w - wv[n][0]] + wv[n][1]) -            dp[i + 1][j] = dp[i][j] +            dp[n + 1][w] = dp[n][w]