← 返回题目

题库练习购物

← 上一题下一题 →

A1939 | $购物$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

你就要去购物了，现在你手上有 $N$ 种不同面值的硬币，每种硬币有无限多个。为了方便购物，你希望带尽量少的硬币，但要能组合出 $1$ 到 $X$ 之间的任意值。

输入格式

第一行两个数 $X, N$，以下 $N$ 个数，表示每种硬币的面值。

输出格式

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

输入输出样例

输入 #1

20 4
1 2 5 10

输出 #1

C++ 编辑器

输入

输出