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