Заполнение коробки
Заполнение коробки
Имеется коробка размера 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