Problem1567--收银员PIPI

1567: 收银员PIPI

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 120  Solved: 23
[Submit] [Status] [Web Board] [Creator:]

Description

PIPI需要找给客人t元，现在他手上有n种面值的纸币，每种纸币的数量可以看作无限多。
他想要使用最少的纸币凑齐这t元，请问这个最小值是多少？

Input

多组输入。
第一行输入要凑齐的钱数t(t<=1e6)和有的纸币种数n(n<=20)。
接下来输入这n种纸币的面值x(xi<=1e9)。

Output

输出凑齐目标钱数的最少纸币数。若无法恰好凑到目前钱数，输出-1。

Sample Input 

10 3
2 3 4

Sample Output 

3

Source/Category

中等 
[Submit] [Status]