P3847 - 马云

题目

P3847马云

限制 : 时间限制 : - MS 空间限制 : 265536 KB

评测说明 : 1000ms

问题描述

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

输入格式

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

输出格式

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

样例输入 1

20 4
1
2
5
10

样例输出 1

样例输入 2

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

样例输出 2

提示

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