Given N items of mass m1, …, mN. They fill a backpack that can withstand a weight of no more than M. How to gain weight in exactly M using as few items as possible?
Input:
- the first line contains a natural number N not exceeding 100 and a natural number M not exceeding 10000;
- the second line contains N natural numbers mi not exceeding 100.
Output: Print the smallest number of items you need, or 0 if you can't gain the given weight.
Examples
| # |
Input |
Output |
| 1 |
1 5968
18
|
0 |