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

itemList = [[0 for _ in range(weightMax+1)] for _ in range(n+1)]



for i in range(n):

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

    for j in reversed(list(range(weightMax+1))):

        if j-w >= 0:

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

        else:

            itemList[i+1][j] = itemList[i][j]

print((max(itemList[n])))

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

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



for i in range(n):

    weight, value = list(map(int,input().split()))

    for w in range(max_weight+1):

        if w >= weight:

            dp[i+1][w] = max(dp[i][w-weight] + value, dp[i][w])

        else:

            dp[i+1][w] = dp[i][w]

print((dp[n][max_weight]))
n, weightMax = list(map(int, input().split()))
itemList = [[0 for _ in range(weightMax + 1)] for _ in range(n + 1)]
for i in range(n):
    w, v = list(map(int, input().split()))
    for j in reversed(list(range(weightMax + 1))):
        if j - w >= 0:
            itemList[i + 1][j] = max([itemList[i][j], itemList[i][j - w] + v])
        else:
            itemList[i + 1][j] = itemList[i][j]
print((max(itemList[n])))

n, max_weight = list(map(int, input().split()))
dp = [[0 for _ in range(max_weight + 1)] for _ in range(n + 1)]
for i in range(n):
    weight, value = list(map(int, input().split()))
    for w in range(max_weight + 1):
        if w >= weight:
            dp[i + 1][w] = max(dp[i][w - weight] + value, dp[i][w])
        else:
            dp[i + 1][w] = dp[i][w]
print((dp[n][max_weight]))

-n, weightMax = list(map(int, input().split())) -itemList = [[0 for _ in range(weightMax + 1)] for _ in range(n + 1)] +n, max_weight = list(map(int, input().split())) +dp = [[0 for _ in range(max_weight + 1)] for _ in range(n + 1)] -    w, v = list(map(int, input().split())) -    for j in reversed(list(range(weightMax + 1))): -        if j - w >= 0: -            itemList[i + 1][j] = max([itemList[i][j], itemList[i][j - w] + v]) +    weight, value = list(map(int, input().split())) +    for w in range(max_weight + 1): +        if w >= weight: +            dp[i + 1][w] = max(dp[i][w - weight] + value, dp[i][w]) -            itemList[i + 1][j] = itemList[i][j] -print((max(itemList[n]))) +            dp[i + 1][w] = dp[i][w] +print((dp[n][max_weight]))