K. Оплата интернета
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Иван — студент Берляндского государственного университета. Начался новый учебный год, и Иван хочет подключить мобильный интернет, поэтому ему нужно внести необходимую сумму на счёт телефона. К сожалению, у Ивана есть только наличные деньги, поэтому всю сумму придётся вносить через банкомат.

В Берляндии существуют купюры девяти различных номиналов: 10, 20, 50, 100, 200, 500, 1 000, 2 000 и 5 000 бурлей (и все эти купюры принимаются банкоматами). У Ивана есть какое-то количество купюр каждого номинала, и он собирается взять какие-то из этих купюр и перевести их на счёт своего мобильного телефона через банкомат. Этих купюр может не хватить, чтобы набрать нужную сумму. Может быть и наоборот: Ивану придётся внести на счёт больше, чем требуется для подключения интернета. Но, если Иван сможет оплатить интернет, то он хочет внести на счёт как можно меньшую сумму, которой будет достаточно для оплаты.

Иван пока не решил, какой именно тариф он хочет подключить. Всего ему доступны q тарифов, i-й из которых характеризуется натуральным числом ki — количеством бурлей, необходимых для подключения интернета по этому тарифу. Иван хочет для каждого из тарифов узнать, хватит ли у него денег на его подключение, и если да, то какую минимальную сумму ему нужно будет внести на счёт (с учётом того, что он выбирает какую-то часть своих купюр для оплаты). Иван уже попытался выполнить все необходимые вычисления самостоятельно, но запутался в них. Помогите Ивану определить нужную ему информацию!

Обратите внимание: Иван в этой задаче не тратит деньги, то есть каждый тариф рассматривается независимо с учётом тех денег, которые были у Ивана изначально.

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

В первой строке следуют 9 целых чисел a10, a20, a50, a100, a200, a500, a1 000, a2 000 и a5 000, где ai равно количеству купюр номинала i, имеющихся у Ивана (0 ≤ ai ≤ 1012).

Во второй строке записано целое число q (1 ≤ q ≤ 105) — количество тарифов.

В третьей строке записаны q целых чисел k1, k2, ..., kq (1 ≤ ki ≤ 1015), где ki равно стоимости подключения интернета по i-му тарифу.

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

В единственную строку выходных данных выведите через пробел q целых чисел. i-е из них должно быть равно минимальной сумме, которую Иван должен внести в банкомат для подключения i-го тарифа (или -1, если Ивану не хватит денег для подключения этого тарифа).

Примеры
Входные данные
0 3 1 0 0 0 0 0 0
4
45 55 70 150
Выходные данные
50 60 70 -1
Входные данные
1 1 1 1 1 1 1 1 1
7
4999 7004 8090 9000 8841 8880 8881
Выходные данные
5000 7010 8100 -1 8850 8880 -1
Примечание

В первом примере у Ивана есть только три купюры номиналом 20 бурлей и одна купюра номиналом 50:

  • для первого тарифа Ивану нужно положить на счет не менее 45 бурлей, для этого ему достаточно взять одну купюру номиналом 50 бурлей;
  • для второго тарифа — не менее 55 бурлей, а потому необходимо использовать три купюры номиналом 20 бурлей;
  • для третьего тарифа — не менее 70 бурлей; данную сумму можно получить, если взять одну купюру номиналом 20 бурлей и одну купюру номиналом 50 бурлей;
  • для четвёртого тарифа у Ивана недостаточно денег, так как необходимо не менее 150 бурлей, а в наличии у него только 3·20 + 1·50 = 110 бурлей.

Во втором примере у Ивана есть по одной купюре каждого достоинства:

  • для первого тарифа Ивану нужно положить на счет не менее 4 999 бурлей, для этого ему достаточно взять одну купюру номиналом 5 000 бурлей, то есть 1·5 000 = 5 000;
  • для второго тарифа — не менее 7 004 бурлей: нужно положить на счёт 1·10 + 1·2 000 + 1·5 000 = 7 010 бурлей;
  • для третьего тарифа — не менее 8 090 бурлей: нужно положить на счёт 1·100 + 1·1 000 + 1·2 000 + 1·5 000 = 8 100 бурлей;
  • для четвёртого тарифа — не менее 9 000 бурлей, денег недостаточно, так как в наличии только 1·10 + 1·20 + 1·50 + 1·100 + 1·200 + 1·500 + 1·1 000 + 1·2 000 + 1·5 000 = 8 880 бурлей;
  • для пятого тарифа — не менее 8 841 бурлей: нужно положить на счёт 1·50 + 1·100 + 1·200 + 1·500 + 1·1 000 + 1·2 000 + 1·5 000 = 8 850 бурлей;
  • для шестого тарифа — не менее 8 880 бурлей, надо взять все имеющиеся купюры;
  • для седьмого тарифа — не менее 8 881 бурлей, денег недостаточно.