Thornhill Computer Club 2024 - April Contest - Problem 5

krem is baking a large cake that requires ~N~ ~(1 \le N \le 5 \cdot 10^4)~ cups of flour. However, all the markings on his ~M~ ~(1 \le 50)~ measurement devices have been erased, leaving him unable to measure precise amounts of flour. Luckily, krem knows the ~i~th measuring device can hold ~C_i~ ~(1 \le i \le M)~ cups of flour when completely filled. Instead of buying new measuring devices, krem wants to know if he can measure exactly ~N~ cups of flour using his ~M~ measuring devices. Can you determine the minimum number of times krem needs to measure out flour only using his ~M~ measuring devices before he has exactly ~N~ cups? If it is impossible to do so, output -1.

Input Specification

The first line will contain two integers ~N~ and ~M~, the number of cups of flour and number of measuring devices.
The next line will contain ~M~ integers ~C_i~, the number of cups of flour the ~i~th measuring device can hold.

Output Specification

Output a single integer, the minimum number of times krem needs to measure out flour. Output -1 if it is impossible.

Sample Input 1

100 3
33 40 1

Sample Output 1

4

Explanation for Sample Output 1

krem can measure out 33 cups of flour three times and 1 cup of flour one time.

Sample Input 2

12 4
1 2 3 4

Sample Output 2

3

Explanation for Sample Output 2

krem can measure out 4 cups of flour three times.

Sample Input 3

203 3
16 33 54

Sample Output 3

-1

Explanation for Sample Output 3

It is impossible for krem to measure out exactly 18 cups of flour using measurement devices of 16, 33, and 54.