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())
v = [0]*N;w = [0]*N

for i in range(N):
    v[i],w[i] = map(int,input().split())

value = [0]*(W+1)
for i in range(N):
    for j in range(w[i],W+1):
        value[j] = max(value[j],value[j-w[i]]+v[i])
    print(value)
print(value[W])
N,W = map(int,input().split())
v = [0]*N;w = [0]*N

for i in range(N):
    v[i],w[i] = map(int,input().split())

value = [0 for i in range(W+1)]
for i in range(N):
    for j in range(W,-1,-1):
        if j<w[i]:
            value[j] = value[j]
        else:
            value[j] = max(value[j],value[j-w[i]]+v[i])

print(value[W])