购物

题目描述

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

输入输出格式

输入格式


第一行两个数X、N,以下N个数,表示每种硬币的面值。 【数据规模】 对于30%的数据,满足N≤3,X≤20; 对于100%的数据,满足N≤10,X≤1000.

输出格式


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

输入输出样例

输入样例 #1

20 4
1 2 5 10

输出样例 #1

5