Problem Description

JokerShaco has a number $x$. Initially, $x=0$, and he wants to change $x$ into $y$. To achieve this, he can use two sets $A$ and $B$. Set $A$ contains $n$ elements, which are all positive integers from $1$ to $n$. Set $B$ contains $m$ elements. Each time, he can perform the following operations on $x$ any number of times:

• Choose an element $a$ from $A$, and add $a$ to $x$.
• Choose an element $b$ from $B$, and multiply $x$ by $b$.

Given $y$, $n$, $m$, and the specific values of the $m$ elements in $B$, JokerShaco wants to know the minimum number of operations needed to make $x$ become $y$.

Input Format

The first line contains three integers $y\ (1\le y\le 5\cdot 10^6)$, $n\ (1\le n\le 5\cdot 10^6)$, and $m\ (1\le m\le 10)$, with meanings as described above.

The second line contains $m$ positive integers. The $i$-th one represents the $i$-th element in $B$, $b_i\ (1\le b_i\le 5\cdot 10^6)$.

Output Format

Output one integer, representing the minimum number of operations needed to make $x$ become $y$. Under the conditions of the problem, it is guaranteed that $x$ can always be changed into $y$.

10 3 1
2

3

100 6 3
2 3 5

3

Hint

Translated by ChatGPT 5