A keyring holds n fobs, each with a whole-number weight. You want to detach a subset of fobs whose weights add up to exactly T, using as few fobs as possible. Each fob may be used at most once. Report the minimum number of fobs needed to reach exactly T, or -1 if no subset of fobs sums to T. Reaching T = 0 needs zero fobs.
Input format
Line 1: two integers n and T.
Line 2: n space-separated integers, the fob weights.
Output format
A single integer: the minimum number of fobs summing to exactly T, or -1 if impossible.
Constraints
- 1 <= n <= 40
- 1 <= each weight <= 1000
- 0 <= T <= 40000