Given N gold bars of mass m1, …, mN. They fill a backpack that can withstand a weight of no more than M. What is the largest amount of gold that can be carried in such a backpack?
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 one integer - the largest possible amount of gold that can be carried in the given backpack.
Examples
| # |
Input |
Output |
| 1 |
2 3195
38 41
|
79 |