# Greedy

# 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 `2`

* ^{i}`2`

* ^{i}`2`

. Find the minimum number of cubes necessary to fill the box, or print ^{i}**-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** ≤ `10`

), and the number ^{6}**k** (**1** ≤ **k** ≤ **20**) of cube types you have. The second line contains **k** positive integers, not greater than `10`

: the ^{6}**i**-th number gives the number of cubes `2`

* ^{i}`2`

* ^{i}`2`

(^{i}**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.

4 4 8 3 10 10 10 4 4 8 3 10 10 1 10 10 11 1 1099

2 9 -1