A. 简单的加法乘法计算题
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

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$$$ 的最少操作次数。

Input

第一行包含三个整数 $$$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)$$$。

Output

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

Examples
Input
10 3 1
2
Output
3
Input
100 6 3
2 3 5
Output
3