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 $22$. 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 11\; \backslash times\; 1$ tiles.

입력

The first line of input contains three integers $W,HW,\; H$ and $NN$ ($1\le W,H\le 2^{50}1\; \backslash leq\; W,H\; \backslash leq\; 2^\{50\}$ and $1\le N\le 511\; \backslash leq\; N\; \backslash leq\; 51$). Here, $WW$ and $HH$ indicate the dimensions of the rectangle. The next line contains $NN$ integers $a_0,a_1,\dots ,a_{N-1}a\_0,\; a\_1,\; \backslash ldots,\; a\_\{N-1\}$ where $a_{i}a\_i$ ($0\le a_i\le 2^{51}0\; \backslash leq\; a\_i\; \backslash leq\; 2^\{51\}$) is the number of $2^i\times 2^{i}2^i\; \backslash times\; 2^i$ squares you own.

출력

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