VK Cup 2015 - Раунд 1 |
---|
Закончено |
Банкоматы одного известного банка одной небольшой страны устроены таким образом, что они могут выдать не любую сумму денег, запрошенную пользователем. Из-за ограниченного размера диспенсера купюр (устройства, непосредственно выдающего деньги в банкомате) и особенностей устройства банкомата, на руки можно получить не более, чем k купюр, при этом купюры могут быть не более, чем двух различных достоинств.
Например, если в стране используются купюры достоинствами 10, 50, 100, 500, 1000 и 5000 бурлей, то при k = 20 подобный банкомат может выдать суммы в 100 000 бурлей и в 96 000 бурлей, а вот суммы в 99 000 бурлей и 101 000 бурлей — уже не может.
Предположим, в стране находятся в хождении купюры n различных достоинств, при этом в банкомате, которым вы пользуетесь, находится неограниченное количество купюр каждого вида. Вы знаете, что в течение дня вам потребуется q раз снять некоторое количество наличных денег. Известно, что банкомат при наличии нескольких способов выдать сумму денег выбирает тот, в котором требуется минимальное количество банкнот, либо выдаёт сообщение об ошибке, если это сделать невозможно. Определите результат каждого из q запросов на выдачу наличных.
В первой строке находятся два целых числа n, k (1 ≤ n ≤ 5000, 1 ≤ k ≤ 20).
В следующей строке находятся n разделённых пробелами целых чисел ai (1 ≤ ai ≤ 107) — достоинства купюр, пребывающих в хождении в стране. Числа ai следуют в строго возрастающем порядке.
В следующей строке находится целое число q (1 ≤ q ≤ 20) — количество запросов на выдачу валюты, которые вы произведёте.
В последующих q строках находятся числа xi (1 ≤ xi ≤ 2·108) — суммы денег в бурлях, которые вы собираетесь получить в банкомате.
На каждый запрос выдачи валюты выведите в отдельной строке минимальное количество банкнот, которым может обойтись банкомат, либо выведите - 1, если выдать соответствующую сумму невозможно.
6 20
10 50 100 500 1000 5000
8
4200
100000
95000
96000
99000
10100
2015
9950
6
20
19
20
-1
3
-1
-1
5 2
1 2 3 5 8
8
1
3
5
7
9
11
13
15
1
1
1
2
2
2
2
-1
Название |
---|