You have $N$ kinds of 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.
• You can select as many items as possible into a knapsack for each kind.

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.