직사각형 타일링

정수 변 길이를 가진 직사각형을 생각하자. 직사각형의 정사각형 타일링은 변이 직사각형의 변과 평행한, 서로 겹치지 않는 정사각형으로 전체 영역을 덮는 것이다. 정사각형 타일링에서 어떤 정사각형도 직사각형의 경계를 넘어가면 안 된다.

한 변의 길이가 $2$의 거듭제곱인 정사각형들을 가지고 있다. 가진 정사각형으로 직사각형을 타일링할 때, 사용하는 정사각형의 개수가 가장 적은 타일링을 찾거나, 타일링이 불가능하다는 것을 알아내라.

그림 1: 처음 세 입력에 대한 최적의 정사각형 타일링. 표시가 없는 작은 타일은 $1 \times 1$ 타일이다.

첫 줄에 세 정수 $W$, $H$, $N$ ($1 \leq W, H \leq 2^{50}$, $1 \leq N \leq 51$)이 주어진다. $W$와 $H$는 직사각형의 가로와 세로 길이이다. 다음 줄에는 $N$개의 정수 $a_0, a_1, \ldots, a_{N-1}$이 주어진다. 여기서 $a_i$ ($0 \leq a_i \leq 2^{51}$)는 가진 $2^i \times 2^i$ 정사각형의 개수이다.

가진 정사각형으로 $W \times H$ 직사각형의 정사각형 타일링이 존재하면, 그 타일링에 필요한 정사각형 개수의 최솟값을 출력한다. 존재하지 않으면 $-1$을 출력한다.