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



wv = []

for _ in range(N):

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



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



for i in range(N):

    wi, vi = wv[i]



    for j in range(wi):

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



    for j in range(wi, W+1):

        dp[i+1][j] = max(dp[i][j], dp[i][j-wi] + vi)



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

# import sys

# sys.setrecursionlimit(10**5)

# from collections import defaultdict

geta = lambda fn: list(map(fn, input().split()))

gete = lambda fn: fn(eval(input()))



N, W = geta(int)

cur = [0] * (W+1) 



for i in range(N):

    w, v = geta(int)

    update = cur[:]

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

        tmp = cur[j-w] + v

        if tmp > cur[j]: update[j] = tmp

    

    cur = update



print((cur[W]))

N, W = list(map(int, input().split()))
wv = []
for _ in range(N):
    wv.append(tuple(map(int, input().split())))
dp = [[0] * (W + 1) for _ in range(N + 1)]
for i in range(N):
    wi, vi = wv[i]
    for j in range(wi):
        dp[i + 1][j] = dp[i][j]
    for j in range(wi, W + 1):
        dp[i + 1][j] = max(dp[i][j], dp[i][j - wi] + vi)
print((dp[N][W]))

# import sys
# sys.setrecursionlimit(10**5)
# from collections import defaultdict
geta = lambda fn: list(map(fn, input().split()))
gete = lambda fn: fn(eval(input()))
N, W = geta(int)
cur = [0] * (W + 1)
for i in range(N):
    w, v = geta(int)
    update = cur[:]
    for j in range(w, W + 1):
        tmp = cur[j - w] + v
        if tmp > cur[j]:
            update[j] = tmp
    cur = update
print((cur[W]))

-N, W = list(map(int, input().split())) -wv = [] -for _ in range(N): -    wv.append(tuple(map(int, input().split()))) -dp = [[0] * (W + 1) for _ in range(N + 1)] +# import sys +# sys.setrecursionlimit(10**5) +# from collections import defaultdict +geta = lambda fn: list(map(fn, input().split())) +gete = lambda fn: fn(eval(input())) +N, W = geta(int) +cur = [0] * (W + 1) -    wi, vi = wv[i] -    for j in range(wi): -        dp[i + 1][j] = dp[i][j] -    for j in range(wi, W + 1): -        dp[i + 1][j] = max(dp[i][j], dp[i][j - wi] + vi) -print((dp[N][W])) +    w, v = geta(int) +    update = cur[:] +    for j in range(w, W + 1): +        tmp = cur[j - w] + v +        if tmp > cur[j]: +            update[j] = tmp +    cur = update +print((cur[W]))