题目描述

育华学校组织同学们去参加校园义卖活动，你需要准备一些零钱用于购物。你有 $N$ 种不同面值的代金券，并且每种代金券有无限多张。为了方便购物，你希望携带最少数量的代金券，同时能够组合出 $1$ 到 $X$ 之间的任意价格。请你编写程序计算出最少需要携带多少张代金券，如果无法满足条件则输出 $-1$。

输入格式

第一行包含两个整数 $X$ 和 $N$，其中 $X$ 表示需要能够组合出的最大价格，$N$ 表示代金券的种类数。

接下来的 $N$ 行，每行一个整数，表示每种代金券的面值。

输出格式

输出一个整数，表示最少需要携带的代金券数量。如果无法满足条件，则输出 $-1$。

样例 #1

样例输入 #1

30 3
1 3 5

样例输出 #1

8

数据范围

对于 $30\%$ 的数据，满足 $N \leq 3$，$X \leq 20$；

对于 $100\%$ 的数据，满足 $N \leq 10$，$X \leq 1000$。