You have $N$ items that you want to put them into a knapsack. Item $i$ has value $v_i$ and weight $w_i$.

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$

$v_1\ w_1$

$v_2\ w_2$

$:$

$v_N\ w_N$

The first line consists of the integers $N$ and $W$. 

In the following lines, the value and weight of the $i$-th item are given.