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 (1 ≤ length, width, height ≤ 106), and the number k (1 ≤ k ≤ 20) 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.