407204: GYM102697 175 Counting Calories (Harder Version)

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.

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 a single positive integer $$$m$$$: the minimum number of food items that you need to eat, in order to have eaten exactly $$$n$$$ calories.

2310
3
500
100
10

8

600
3
500
300
1

2

10000
3
3
7
11

912

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.