P3847 - 马云

Problem

P3847马云

Limits : Time Limit : - MS Memory Limit : 265536 KB

Judgment Tips : 1000ms

Description

Mr_he 因讨厌马云而彻底放弃网购，他的日常用品都要到商场去购买，而且必须付现金。但是现金购买，经常会遇到找零的问题，那么现在请你帮助他解决这样一个问题：现在 Mr_he 手上有 n 种不同面值的硬币，每种硬币有无限多个。为了方便购物，他希望带尽量少的硬币，但是要能组合出 1 到 m 之间的任意值。

Input Format

第一行为两个整数：m 和 n，他们的意义如题目描述。
接下来的 n 行，每行一个整数，第 i+1 行的整数表示第 i 种硬币的面值

Output Format

最少需要携带的硬币数量，如果无解则输出-1。

Sample Input 1

20 4
1
2
5
10

Sample Output 1

Sample Input 2

2008 20
73
10
39
46
77
44
67
1
26
29
80
61
10
42
20
66
53
50
8
59

Sample Output 2

Hint

【数据范围】
50%的数据：1<=n<=10， 1<=m<=10^3；
100%的数据：1<=n<=100，1<=m<=10^9；