A caravan crate must be packed to exactly C kilograms - shifting cargo is forbidden, so any slack is unacceptable. There are n goods; good i weighs w_i and is worth v_i. Each good may be packed at most once. Among all subsets whose total weight is exactly C, report the maximum total value. If no subset weighs exactly C, report -1. Note C = 0 is achieved by the empty subset with value 0.
Line 1: two integers n and C.
Next n lines: two integers w_i and v_i for each good.
A single integer: the maximum value of a subset weighing exactly C, or -1 if none exists.
Example 1
Input
3 5 2 3 3 4 5 10
Expected
10
Explanation
Two subsets weigh exactly 5: {2,3}-goods with value 7, and the single 5-good with value 10; the best is 10.
Example 2
Input
2 4 3 5 5 8
Expected
-1
Explanation
The only subset weights are 0, 3, 5 and 8; none equals 4, so the crate cannot be exactly filled and the answer is -1.
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 →