n, w = list(map(int, input().split()))

wt, v = [], []

for i in range(n):

    a, b = list(map(int, input().split()))

    wt.append(a)

    v.append(b)

dp = [[0 for i in range(w + 1)] for j in range(n + 1)]

for i in range(1, len(wt)+1):

    for j in range(w + 1):

        if j >= wt[i-1]:

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

        else:

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

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

n, w = list(map(int, input().split()))

wt, v = [], []

for i in range(n):

    a, b = list(map(int, input().split()))

    wt.append(a)

    v.append(b)

dp = [0 for i in range(w + 1)]

for i in range(len(wt)):

    for j in range(w, wt[i]-1, -1):

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

print((dp[-1]))

n, w = list(map(int, input().split()))
wt, v = [], []
for i in range(n):
    a, b = list(map(int, input().split()))
    wt.append(a)
    v.append(b)
dp = [[0 for i in range(w + 1)] for j in range(n + 1)]
for i in range(1, len(wt) + 1):
    for j in range(w + 1):
        if j >= wt[i - 1]:
            dp[i][j] = max(dp[i - 1][j], v[i - 1] + dp[i - 1][j - wt[i - 1]])
        else:
            dp[i][j] = dp[i - 1][j]
print((dp[-1][-1]))

n, w = list(map(int, input().split()))
wt, v = [], []
for i in range(n):
    a, b = list(map(int, input().split()))
    wt.append(a)
    v.append(b)
dp = [0 for i in range(w + 1)]
for i in range(len(wt)):
    for j in range(w, wt[i] - 1, -1):
        dp[j] = max(dp[j], v[i] + dp[j - wt[i]])
print((dp[-1]))

-dp = [[0 for i in range(w + 1)] for j in range(n + 1)] -for i in range(1, len(wt) + 1): -    for j in range(w + 1): -        if j >= wt[i - 1]: -            dp[i][j] = max(dp[i - 1][j], v[i - 1] + dp[i - 1][j - wt[i - 1]]) -        else: -            dp[i][j] = dp[i - 1][j] -print((dp[-1][-1])) +dp = [0 for i in range(w + 1)] +for i in range(len(wt)): +    for j in range(w, wt[i] - 1, -1): +        dp[j] = max(dp[j], v[i] + dp[j - wt[i]]) +print((dp[-1]))