You have N items that you want to put them into a knapsack. Item i has value vi and weight wi.  You want to find a subset of items to put such that:    * The total value of the items is as large as possible.   * The items have combined weight at most W, that is capacity of the knapsack.  Find the maximum total value of items in the knapsack.
n, w = map(int, input().split())

values = [0]
weights = [0]
for i in range(n):
    value, weight = map(int, input().split())
    values.append(value)
    weights.append(weight)

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

for i in range(len(values)):
    for j in range(w + 1):
        if weights[i] <= j:
            dp[i + 1][j] = max(dp[i][j - weights[i]] + values[i], dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]

print(dp[n][w])


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

values = []
weights = []
for i in range(n):
    value, weight = map(int, input().split())
    values.append(value)
    weights.append(weight)

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

for i in range(n):
    for j in range(w + 1):
        if weights[i] <= j:
            dp[i + 1][j] = max(dp[i][j - weights[i]] + values[i], dp[i][j])
        else:
            dp[i + 1][j] = dp[i][j]

print(dp[n][w])

