购物
题目描述
你就要去购物了,现在你手上有 $N$ 种不同面值的硬币,每种硬币有无限多个。为了方便购物,你希望带尽量少的硬币,但要能组合出 $1$ 到 $X$ 之间的任意值。
输入输出格式
输入格式
第一行两个数 $X, N$,以下 $N$ 个数,表示每种硬币的面值。
输出格式
最少需要携带的硬币个数,如果无解输出 `-1`。
输入输出样例
输入样例 #1
20 4
1 2 5 10
输出样例 #1
5
说明
对于 $30\%$ 的数据,满足 $N \le 3$,$X \le 20$;
对于 $100\%$ 的数据,满足 $N \le 10$,$X \le 10^3$。