import sys

input = sys.stdin.readline



N, W = [int(x) for x in input().split()]

wv = []

for _ in range(N):

    wv.append([int(x) for x in input().split()])



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



for i in range(N):

    for j in range(W + 1):

        w, v = wv[i]

        if j >= w:

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

        else:

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



print((dp[N][W]))
import sys

input = sys.stdin.readline



n, W = [int(x) for x in input().split()]

wv = [[int(x) for x in input().split()] for _ in range(n)]



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



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

    w, v = wv[i - 1]

    for j in range(W + 1):

        if j - w >= 0:

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

        else:

            dp[i][j] = dp[i - 1][j]



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

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

import sys

input = sys.stdin.readline
n, W = [int(x) for x in input().split()]
wv = [[int(x) for x in input().split()] for _ in range(n)]
dp = [[0] * (W + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    w, v = wv[i - 1]
    for j in range(W + 1):
        if j - w >= 0:
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w] + v)
        else:
            dp[i][j] = dp[i - 1][j]
print((dp[-1][-1]))

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