题目描述

JokerShaco 有一个数字 $x$，最开始 $x=0$，他想要把 $x$ 变成 $y$。为了达到这个目标，他可以利用两个集合 $A$ 和 $B$。其中集合 $A$ 包含 $n$ 个元素，分别是从 $1$ 到 $n$ 的所有正整数；集合 $B$ 包含 $m$ 个元素。每次它可以对 $x$ 进行如下任意次操作：

• 选择 $A$ 中的一个元素 $a$，令 $x$ 加上 $a$。
• 选择 $B$ 中的一个元素 $b$，令 $x$ 乘以 $b$。

已知 $y$，$n$，$m$ 和 $B$ 中 $m$ 个元素的具体值，JokerShaco 想知道让 $x$ 变成 $y$ 的最少操作次数。

输入格式

第一行包含三个整数 $y\ (1\le y\le 5\cdot 10^6)$，$n\ (1\le n\le 5\cdot 10^6)$ 和 $m\ (1\le m\le 10)$，其含义如题目所述。

第二行包含 $m$ 个正整数，其中第 $i$ 个表示 $B$ 中的第 $i$ 个元素 $b_i\ (1\le b_i\le 5\cdot 10^6)$。

输出格式

输出一个整数，表示让 $x$ 变成 $y$ 的最少操作次数。在题目条件下可知一定能将 $x$ 变成 $y$。

输入输出样例

10 3 1
2

3

100 6 3
2 3 5

3

100 24 2
1 9

3