Paintings

Bajtazar has just moved into a new apartment. After decorating the shelves with trophies from recitation contests and the Bajtocja yodeling championships, he noticed that one wall is completely empty. He wants to fill it with paintings.

The wall is a rectangle of size $h \times w$ meters. A nearby art dealer, a close friend of Bajtazar, sells $n$ kinds of paintings, and there is an unlimited supply of each kind. All paintings of the same kind have the same size: paintings of the $i$-th kind are squares with side length $d_i$ meters. For any two different values of $d_i$, one is divisible by the other.

Bajtazar does not care about the price, but he wants no empty space left on the wall. The paintings may not overlap, but they may touch along their edges. He does not want to walk back and forth to the dealer many times, so he wants to buy as few paintings as possible. Compute the minimum number of paintings needed to cover the wall, or determine that covering the wall is impossible.

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

The second line contains one integer $n$ ($1 \le n \le 30$), the number of kinds of paintings.

The third line contains $n$ distinct integers $d_1, d_2, \ldots, d_n$ ($1 \le d_i \le 10^9$, $d_i < d_{i+1}$, and $d_{i+1}$ is divisible by $d_i$), the sizes of the paintings of each kind.

If the wall can be covered, print one integer, the minimum number of paintings needed to cover it. Otherwise, print -1.

In the first sample, Bajtazar can cover the wall with nine paintings: six of size 1 by 1, two of size 3 by 3, and one of size 6 by 6, arranged as shown in the image below.

In the second sample, it is impossible to cover the wall exactly.