N, W = (int(n) for n in input().split())

w, v = [], []

for _ in range(N):

    w_, v_ = (int(n) for n in input().split())

    w.append(w_)

    v.append(v_)



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



for i in range(N):

    for w_ in range(W + 1):

        if w_ >= w[i]:

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

        else:

            dp[i + 1][w_] = dp[i][w_]



print((dp[N][W]))
N, weight_capacity = (int(n) for n in input().split())

weights, values = [], []

for _ in range(N):

    w, v = (int(n) for n in input().split())

    weights.append(w)

    values.append(v)



def knapsack_dp(weight_capacity, weights, values):

    """Solve knapsack problem by dynamic programming"""

    N = len(weights)

    dp = [[0] * (weight_capacity + 1) for _ in range(len(weights) + 1)]



    for i in range(N):

        for w in range(weight_capacity + 1):

            if w >= weights[i]:

                dp[i + 1][w] = max(dp[i][w], dp[i][w - weights[i]] + values[i])

            else:

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



    return dp[N][weight_capacity]



print((knapsack_dp(weight_capacity, weights, values)))

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

N, weight_capacity = (int(n) for n in input().split())
weights, values = [], []
for _ in range(N):
    w, v = (int(n) for n in input().split())
    weights.append(w)
    values.append(v)


def knapsack_dp(weight_capacity, weights, values):
    """Solve knapsack problem by dynamic programming"""
    N = len(weights)
    dp = [[0] * (weight_capacity + 1) for _ in range(len(weights) + 1)]
    for i in range(N):
        for w in range(weight_capacity + 1):
            if w >= weights[i]:
                dp[i + 1][w] = max(dp[i][w], dp[i][w - weights[i]] + values[i])
            else:
                dp[i + 1][w] = dp[i][w]
    return dp[N][weight_capacity]


print((knapsack_dp(weight_capacity, weights, values)))

-N, W = (int(n) for n in input().split()) -w, v = [], [] +N, weight_capacity = (int(n) for n in input().split()) +weights, values = [], [] -    w_, v_ = (int(n) for n in input().split()) -    w.append(w_) -    v.append(v_) -dp = [[0] * (W + 1) for _ in range(N + 1)] -for i in range(N): -    for w_ in range(W + 1): -        if w_ >= w[i]: -            dp[i + 1][w_] = max(dp[i][w_], dp[i][w_ - w[i]] + v[i]) -        else: -            dp[i + 1][w_] = dp[i][w_] -print((dp[N][W])) +    w, v = (int(n) for n in input().split()) +    weights.append(w) +    values.append(v) + + +def knapsack_dp(weight_capacity, weights, values): +    """Solve knapsack problem by dynamic programming""" +    N = len(weights) +    dp = [[0] * (weight_capacity + 1) for _ in range(len(weights) + 1)] +    for i in range(N): +        for w in range(weight_capacity + 1): +            if w >= weights[i]: +                dp[i + 1][w] = max(dp[i][w], dp[i][w - weights[i]] + values[i]) +            else: +                dp[i + 1][w] = dp[i][w] +    return dp[N][weight_capacity] + + +print((knapsack_dp(weight_capacity, weights, values)))