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

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



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



for i in range(N) :

    weight_i,value_i = L[i]

    for weight in range(W+1) :

        if weight - weight_i >= 0 :

            dp[i+1][weight] = max(dp[i][weight], dp[i][weight - weight_i] + value_i)

        else :

            dp[i+1][weight] = dp[i][weight]



ans = dp[N][W]



print(ans)

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

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



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

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

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

        if j < a :

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

        else :

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



print((dp[n][w]))



N, W = list(map(int, input().split()))
L = [list(map(int, input().split())) for i in range(N)]
dp = [[0 for i in range(W + 1)] for j in range(N + 1)]
for i in range(N):
    weight_i, value_i = L[i]
    for weight in range(W + 1):
        if weight - weight_i >= 0:
            dp[i + 1][weight] = max(dp[i][weight], dp[i][weight - weight_i] + value_i)
        else:
            dp[i + 1][weight] = dp[i][weight]
ans = dp[N][W]
print(ans)

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

-N, W = list(map(int, input().split())) -L = [list(map(int, input().split())) for i in range(N)] -dp = [[0 for i in range(W + 1)] for j in range(N + 1)] -for i in range(N): -    weight_i, value_i = L[i] -    for weight in range(W + 1): -        if weight - weight_i >= 0: -            dp[i + 1][weight] = max(dp[i][weight], dp[i][weight - weight_i] + value_i) +n, w = list(map(int, input().split())) +dp = [[0] * (w + 1) for i in range(n + 1)] +for i in range(1, n + 1): +    a, v = list(map(int, input().split())) +    for j in range(1, w + 1): +        if j < a: +            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) -            dp[i + 1][weight] = dp[i][weight] -ans = dp[N][W] -print(ans) +            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - a] + v) +print((dp[n][w]))