Codeforces Round 494 (Div. 3) |
---|
Закончено |
У Поликарпа есть $$$n$$$ монет, достоинство $$$i$$$-й монеты равно $$$a_i$$$. Гарантируется, что все достоинства являются натуральными степенями $$$2$$$ (то есть $$$a_i = 2^d$$$ для некоторого неотрицательного целого числа $$$d$$$).
Поликарп хочет знать ответы на $$$q$$$ запросов. $$$j$$$-й описывается целым числом $$$b_j$$$. Ответом на запрос является минимальное количество монет, необходимое для получения суммы $$$b_j$$$, используя некоторое подмножество монет (Поликарп может использовать только те монеты, которые у него есть). Если Поликарп не может получить значение $$$b_j$$$, то ответ на $$$j$$$-й запрос равен -1.
Запросы независимы (ответ на запрос не влияет на монеты Поликарпа).
Первая строка входных данных содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$) — количество монет и количество запросов.
Вторая строка входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ — достоинства монет ($$$1 \le a_i \le 2 \cdot 10^9$$$). Гарантируется, что все $$$a_i$$$ являются натуральными степенями $$$2$$$ (то есть $$$a_i = 2^d$$$ для некоторого неотрицательного целого числа $$$d$$$).
Следующие $$$q$$$ строк содержат по одному числу каждая. $$$j$$$-я строка содержит одно целое число $$$b_j$$$ — значение $$$j$$$-го запроса ($$$1 \le b_j \le 10^9$$$).
Выведите $$$q$$$ целых чисел $$$ans_j$$$. $$$j$$$-е число должно равняться ответу на $$$j$$$-й запрос. Если Поликарп не может получить значение $$$b_j$$$, ответ на $$$j$$$-й запрос равен -1.
5 4
2 4 8 2 4
8
5
14
10
1
-1
3
2
Название |
---|