e-olymp
favorite We need a little bit of your help to keep things running, click on this banner to learn more

Fill the Box

You have a length * width * height box, and you want to fill it with cubes. The cubes have sides that are powers of two (1 * 1 * 1, 2 * 2 * 2, 4 * 4 * 4, 8 * 8 * 8, ...). You are given the number of cubes you have. All the cubes have dimention 2i * 2i * 2i. Find the minimum number of cubes necessary to fill the box, or print -1 if it is impossible to do so.

Input

Consists of multiple test cases. The first line of each test case contains the values of length, width, height (1length, width, height106), and the number k (1k20) of cube types you have. The second line contains k positive integers, not greater than 106: the i-th number gives the number of cubes 2i * 2i * 2i (i takes the values from 0 to k - 1) you have.

Output

For each test case print in a separate line the minimum number of cubes necessary to fill the box, or -1 if it is impossible to do so.

Time limit 1 second
Memory limit 128 MiB
Input example #1
4 4 8 3
10 10 10
4 4 8 3
10 10 1
10 10 11 1
1099
Output example #1
2
9
-1