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.
Input format
Line 1: two integers n and C.
Next n lines: two integers w_i and v_i for each good.
Output format
A single integer: the maximum value of a subset weighing exactly C, or -1 if none exists.
Constraints
- 1 <= n <= 40
- 0 <= C <= 2000
- 1 <= w_i <= 1000
- 1 <= v_i <= 1000