Заповнення коробки
Заповнення коробки
Є коробка розміром length * width * height, яку необхідно заповнити кубами. Довжини сторін кубів що є у Вас, є степенями двійки (1 * 1 * 1, 2 * 2 * 2, 4 * 4 * 4, 8 * 8 * 8, ...). Вам задается кількість кубів розміру 2^i
* 2^i
* 2^i
, що є у Вас в наявності. Знайти найменшу кількість кубів, якими можна повністю заповнити коробку, або вивести -1, якщо цього здійснити неможливо.
Вхідні дані
Складається з декількох тестів. Перший рядок кожного тесту містить значення length, width, height (1 ≤ length, width, height ≤ 10^6
), а також кількість k (1 ≤ k ≤ 20) типів кубів, що є у Вас. Другий рядок містить k натуральних чисел, не більших за 10^6
: i-те число задає кількість кубів розміру 2^i
* 2^i
* 2^i
(i приймає значення від 0 до k - 1), якими Ви володієте.
Вихідні дані
Для кожного тесту в окремому рядку вивести найменшу кількість кубів, якими можна повністю заповнити коробку, або -1, якщо цього здійснити неможливо.
Приклад
4 4 8 3 10 10 10 4 4 8 3 10 10 1 10 10 11 1 1099
2 9 -1