Knapsack - MarisaOJ: Marisa Online Judge

Knapsack

Time limit: 1000 ms
Memory limit: 256 MB
There are $n$ items, $i^{th}$ item has the weight of $w_i$ and value of $v_i$. You can choose an arbitrary number items as long as their weight doesn't exceed a given $S$. Find a way of choosing items so that their value is maximum possible. ### Input - First line contains 2 integers $n$ and $S$. - Each line in the next $n$ line contains 2 integers $w_i$, $v_i$. ### Output - The maximum possible value you can obtain. ### Constraints - $1 \le n \le 20, S \le 10^9$. - $1 \le w_i, v_i \le 10^9$. ### Example Input: ``` 3 5 1 4 4 1 2 100 ``` Output: ``` 104 ```