A spelunker's satchel can hold at most C grams. In the cavern lie n gems; gem i weighs w_i grams and is worth v_i coins. Each gem may be taken at most once. Choose a subset of gems whose total weight is at most C so that their total value is as large as possible. Report that maximum total value (0 if nothing can be taken).
Line 1: two integers n and C.
Next n lines: two integers w_i and v_i for each gem.
A single integer: the maximum total value of a subset with total weight at most C.
Example 1
Input
3 5 4 5 2 3 3 4
Expected
7
Explanation
Taking the second gem (weight 2, value 3) and third gem (weight 3, value 4) uses weight 5 for value 7, beating the single first gem's value 5.
Example 2
Input
2 1 2 10 3 20
Expected
0
Explanation
Both gems weigh more than the capacity of 1, so none can be taken and the best value is 0.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →