Question
Minimum Bags for Fruits
Alex has harvested N kilograms of fruits and needs to pack them for transport. He has M types of polybags available, each with a specific capacity, p[i], indicating how many kilograms it can hold. Can you help Alex figure out the minimum number of polybags he’ll need to carry all N kilograms of fruits?
Input
The first line of the input contains two integers N and M.
The second line of the input contains M space-separated integers.
Constraints
1 ≤ N ≤ 1012
1 ≤ M ≤ 105
1 ≤ pi ≤ 108
The second line of the input contains M space-separated integers.
Constraints
1 ≤ N ≤ 1012
1 ≤ M ≤ 105
1 ≤ pi ≤ 108
Output
Print the minimum number of polybags required to carry all N-kilograms of fruits.
Example
Sample Input
10 4
4 9 8 2
Sample Output
2
Explanation
We can carry fruits in polybag 1 and polybag 3. This will give us a total capacity of 4 + 8 = 12 kilograms which is more than that required to carry the fruits.
10 4
4 9 8 2
Sample Output
2
Explanation
We can carry fruits in polybag 1 and polybag 3. This will give us a total capacity of 4 + 8 = 12 kilograms which is more than that required to carry the fruits.