Имеется коробка размера length * width * height, которую необходимо заполнить кубами. Длины сторон имеющихся кубов являются степенями двойки (1 * 1 * 1, 2 * 2 * 2, 4 * 4 * 4, 8 * 8 * 8, ...). Вам задается количество имеющихся у Вас кубов размера 2i * 2i * 2i. Найти наименьшее количество кубов, которыми можно полностью заполнить коробку, или вывести -1, если этого совершить невозможно.

Входные данные

Состоит из нескольких тестов. Первая строка каждого теста содержит значения length, width, height (1 ≤ length, width, height ≤ 106), а также количество k (1 ≤ k ≤ 20) имеющихся у Вас типов кубов. Вторая строка содержит k натуральных чисел, не больших 106: i-ое число задает количество кубов размера 2i * 2i * 2i (i принимает значения от 0 до k - 1), которыми Вы владеете.

Выходные данные

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