You are likely familiar with the story of Henry and Lisa and the hole in the bucket. Not too many people know what happened after Henry managed to fix the hole in his bucket. Lisa, after the hole affair, was pretty upset with Henry. In an effort to get him to think, she had him fill a barrel with several different buckets. The barrel had to be filled exactly to the top by whole (or is that hole?) bucket quantities. Henry, being lazy (which programmers can fully understand), kept thinking about it until he could do it in the fewest buckets possible. Write a program that will output the smallest number of buckets needed to be used to fill a barrel with a given volume. The volume will never exceed ~100~, and the total number of buckets will not be larger than ~100~.

Input Specification

The input will have a series of test cases. For each case the first line will contain two numbers ~M~, ~N~; the volume of the barrel to be filled and the number of different buckets available. This line will be followed by ~N~ lines representing sizes of individual buckets. The end of file will be indicated by a barrel with zero volume.

Output Specification

For every case, the output should be the smallest number of bucket-fulls needed to fill the barrel. If it is not possible to exactly fill the given barrel, output -1.

Sample Input

4 2
3
1
17 4
1
2
4
5
20 3
8
5
1
0 0

Sample Output

2
4
4