#P1658. 购物

购物

题目描述

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

输入格式

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

输出格式

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

20 4
1 2 5 10

5

提示

对于 30%30\% 的数据,满足 N3N \le 3X20X \le 20

对于 100%100\% 的数据,满足 N10N \le 10X103X \le 10^3