Problem Description

Translated from PA 2024 Round 3 Obrazy, thanks to Macaronlin for providing the translation

Given a rectangular wall with dimensions $h \times w$, and $n$ types of square picture frames, each type having an infinite supply. For any two different sizes of frames, the side length of one can always be divided by the side length of the other without a remainder.

You need to completely cover the wall with these frames such that the frames do not overlap but can touch at the edges. Determine the minimum number of frames required to achieve this. If it is impossible to cover the wall completely, the program should output $-1$.

Input Format

The first line contains two integers $h$ and $w\ (1 \le h, w \le 10^9)$, representing the dimensions of the wall.

The second line contains an integer $n\ (1 \le n \le 30)$, indicating the number of different frame sizes.

The third line contains $n$ integers $d_1, d_2, \ldots, d_n\ (1 \le d_i \le 10^9, d_i < d_{i+1})$, representing the sizes of the square frames, ensuring that $d_{i+1}$ is divisible by $d_i$.

Output Format

Output a single integer. If the wall can be completely covered, output the minimum number of frames required; otherwise, output $-1$.

Sample Input and Output

Sample Input #1

6 10
3
1 3 6

Sample Output #1

9

Sample Input #2

3 3
1
2

Sample Output #2

-1

Notes

In the first example, Byteasar can cover the wall with nine frames (six $1 \times 1$, two $3 \times 3$, and one $6 \times 6$), as illustrated below:

In the second example, it is impossible to completely cover the wall.

见题面 Input 部分

见题面 Output 部分