Bajtazar has just moved into a new apartment. Having already decorated his shelves with trophies from various recitation contests and the Bajtocja championships in speed yodeling, he noticed that one wall is completely empty. He didn't like this, so he would like to fill it with paintings.

Bajtazar's wall is a rectangle with dimensions $h \times w$ meters. A nearby art dealer, who is a close friend of Bajtazar, offers $n$ types of paintings, and he has an unlimited supply of each type. All paintings of the same type have exactly the same dimensions – paintings of the $i$-th type are always squares with a side length of $d_i$ meters. Interestingly, for any two different values $d_i$, one is divisible by the other without a remainder.

For Bajtazar, the price of the paintings does not matter (after all, the prizes at the speed yodeling championships are quite substantial), but he wants to ensure that no empty space is left on the wall. To this end, he decided to purchase a certain number of paintings and hang them on the wall so as to cover it completely. Of course, the paintings cannot overlap, but they can touch at their edges. However, Bajtazar does not want to walk to the art dealer too many times – he would like to buy as few paintings as possible. Help him and write a program that will calculate for him how many paintings he must buy, or state that covering the wall is not possible!

Input

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

The second line of the input contains a single integer $n$ ($1 \le n \le 30$) – the number of types of paintings.

The third line of the input contains a sequence of $n$ distinct integers $d_1, d_2, \dots, d_n$ ($1 \le d_i \le 10^9$; $d_i < d_{i+1}$; $d_{i+1}$ is divisible by $d_i$ without a remainder) – the dimensions of the paintings of successive types.

Output

If covering the wall is possible, the output should contain a single integer in one line, representing the minimum possible number of paintings needed to cover the wall. Otherwise, the line should contain the number $-1$.

Examples

Input 1

6 10
3
1 3 6

Output 1

9

Note 1

In the first example test, Bajtazar can cover the wall with nine paintings (six of size $1 \times 1$, two of size $3 \times 3$, and one of size $6 \times 6$), for example in the following way:

Input 2

3 3
1
2

Output 2

-1

Note 2

In the second example test, it is not possible to cover the wall exactly.