There's a Hole in the Bucket

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

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

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

SAMPLE INPUT

Input file

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

Output file

2
4
4

All Submissions
Best Solutions

Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Feb 24, 2009

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Should consider adding some test cases.
I completely forgot to implement the "output -1 if..." portion and i got AC.

This looks a lot like coin change, in fact, I used my coin change code and just modified it a bit and it worked perfectly, effectively giving me twice the points for no additional skill (10 points for CC and 10 points for this). The difference between this and CC is that here you need to do it more than once, but the volume and size of the buckets are a lot smaller. I'm not saying that this is a mayor problem, just saying that it's basically given me more internet points than I deserve.

There can be many reasons for duplicate problems on online judges. For example, you may want to test the users' knowledge on some standard algorithm (like this one), or it may not be practical to go though your whole database to find if a problem has been added before. Also, the analysis shows that the admins know about other similar problems to this one on the judge.