175. Counting Calories (Harder Version)
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Over the quarantine season, you decide to watch your weight by limiting yourself to a certain amount of calories a day.

In this problem, you're given the number of calories of each food item in your house as input.

You want to figure out the minimum number of food items that you need to eat in order to have eaten exactly $$$n$$$ calories.

Input

The first line of input contains a single positive integer $$$n$$$: the target number of calories.

The second line of input contains a single positive integer $$$k$$$: the number of food items.

The next $$$k$$$ lines each contain a single positive integer $$$c$$$: the number of calories of each food item.

Output

Output a single positive integer $$$m$$$: the minimum number of food items that you need to eat, in order to have eaten exactly $$$n$$$ calories.

Examples
Input
2310
3
500
100
10
Output
8
Input
600
3
500
300
1
Output
2
Input
10000
3
3
7
11
Output
912
Note

This problem is not as easy as you think it is. The solution to the easier version of the problem does not correctly solve the second example case.