考虑一个边长为整数的矩形。矩形的方形平铺是指使用互不重叠的方形覆盖整个区域，且这些方形的边与矩形的边平行。在方形平铺中，任何方形都不得超出矩形的边界。

你拥有一系列边长为 2 的幂的方形。请找出使用最少数量的方形来平铺该矩形的方法，或者指出无法完成平铺。

图 I.1：前三个样例输入的最优方形平铺。图中未标注的小方块为 $1 \times 1$ 的瓷砖。

输入格式

输入的第一行包含三个整数 $W, H$ 和 $N$ ($1 \le W, H \le 2^{50}$ 且 $1 \le N \le 51$)。其中 $W$ 和 $H$ 表示矩形的尺寸。下一行包含 $N$ 个整数 $a_0, a_1, \dots, a_{N-1}$，其中 $a_i$ ($0 \le a_i \le 2^{51}$) 是你拥有的 $2^i \times 2^i$ 方形的数量。

输出格式

如果可以使用你拥有的方形平铺 $W \times H$ 的矩形，输出在此类平铺中所需的最少方形数量。否则，如果无法使用你拥有的方形平铺该矩形，输出 $-1$。

样例

输入 1

4 2 2
5 1

输出 1

5

输入 2

6 7 3
10 10 10

输出 2

12

输入 3

17 20 5
20 0 4 0 1

输出 3

25

输入 4

4 2 3
3 1 10

输出 4

-1