eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Заповнення коробки

Заповнення коробки

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Є коробка розміром 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 (1length, width, height10^6), а також кількість k (1k20) типів кубів, що є у Вас. Другий рядок містить k натуральних чисел, не більших за 10^6: i-те число задає кількість кубів розміру 2^i * 2^i * 2^i (i приймає значення від 0 до k - 1), якими Ви володієте.

Вихідні дані

Для кожного тесту в окремому рядку вивести найменшу кількість кубів, якими можна повністю заповнити коробку, або -1, якщо цього здійснити неможливо.

Приклад

Вхідні дані #1
4 4 8 3
10 10 10
4 4 8 3
10 10 1
10 10 11 1
1099
Вихідні дані #1
2
9
-1