Problem K
Rectangle Tiling

Consider a rectangle with integer side lengths. A square tiling of the rectangle is a covering of the entire region using non-overlapping squares whose sides are parallel with those of the rectangle. In a square tiling, no square may overhang (extend beyond the rectangle’s boundary).

You have a collection of squares with side lengths being powers of $2$. Find a square tiling of the rectangle using the fewest squares possible, or, indicate that it cannot be done.

Figure 1: Optimal square tilings for the first three sample inputs. The small unlabelled tiles are $1 \times 1$ tiles.

Input

The first line of input contains three integers $W, H$ and $N$ ($1 \leq W,H \leq 2^{50}$ and $1 \leq N \leq 51$). Here, $W$ and $H$ indicate the dimensions of the rectangle. The next line contains $N$ integers $a_0, a_1, \ldots , a_{N-1}$ where $a_i$ ($0 \leq a_i \leq 2^{51}$) is the number of $2^i \times 2^i$ squares you own.

Output

If there is a square tiling of a $W \times H$ rectangle using the squares you own, output the minimum number of squares needed in such a square tiling. Otherwise, output $-1$ if there is no square tiling of the rectangle using the squares you own.

4 2 2
5 1

5

6 7 3
10 10 10

12

17 20 5
20 0 4 0 1

25

4 2 3
3 1 10

-1