Harddp
0-1 Knapsack
Time limit 2 s · Memory 64 MBAcceptance: —Solved by: 0
Statement
The first line contains the number of items n and the knapsack capacity W. Each of the next n lines contains the weight w and the value v of an item. Print the maximum total value of a set of items whose total weight does not exceed W. Each item may be taken at most once.
Examples
Example 1
Input
3 8 3 30 4 50 5 60
Output
90
Example 2
Input
1 1 2 100
Output
0
Constraints
- 1 ≤ n ≤ 100
- 1 ≤ W ≤ 10^4
- 1 ≤ w ≤ 10^4
- 1 ≤ v ≤ 10^9