Processing math: 100%
Knapsack - MarisaOJ: Marisa Online Judge

Knapsack

Time limit: 1000 ms
Memory limit: 256 MB
There are n items, ith item has the weight of wi and value of vi. 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 wi, vi. ### Output - The maximum possible value you can obtain. ### Constraints - 1≤n≤20,S≤109. - 1≤wi,vi≤109. ### Example Input: 3514412100 Output: 104