После тяжелого контеста бывает полезно выпить немного кофе. У настоящих программистов есть множество различных сортов кофе, которые постепенно добавляются в одну кружку. При этом мы будем рассматривать кофе с определенной особенностью: разные сорта кофе держатся в кружке «слоями» и не перемешиваются.
Напиток из таких сортов кофе можно описать следующим образом: всего в кружку налито $$$n$$$ сортов, $$$i$$$-й сорт характеризуется уровнем крепости $$$p_i$$$ и высотой слоя, который он занимает в кружке, $$$h_i$$$. При этом если $$$i < j$$$, то слой кофе $$$i$$$-го сорта находится ниже кофе $$$j$$$-го сорта. Также известно, что высота кружки равна $$$\sum\limits_{i=1}^n h_i$$$, то есть верхний край самого верхнего слоя кофе находится ровно на уровне верхней границы кружки.
Для разнообразия иногда хочется получить из такого «коктейля» напиток определенного суммарного уровня крепости. Суммарный уровень крепости определяется как среднее взвешенное уровней налитых в кружку сортов, то есть как $$$$$$P = \frac{\sum\limits_{i=1}^n p_i \cdot h_i}{\sum\limits_{i=1}^n h_i} \text{.}$$$$$$
Чтобы как-то изменять $$$P$$$, можно
При выпивании какого-то количества кофе из одного слоя высота этого слоя уменьшается на соответствующую величину, а все верхние слои опускаются на ту же величину вниз.
Ваша задача — ответить на запросы вида: можно ли из текущего напитка сделать напиток крепости $$$t_i$$$, и если можно, то какая минимальная высота трубочки для этого понадобится. Поскольку идеально точную необходимую высоту трубочки вычислить может быть сложно, достаточно определить минимальное количество верхних слоев кофе, достаточное, чтобы, отпив какое-то количество кофе из некоторых из них, можно было добиться суммарной крепости напитка $$$t_i$$$.
В первой строке ввода даны два целых числа $$$n$$$ и $$$q$$$ — количество слоев кофе в кружке и количество запросов ($$$1 \le n, q \le 2 \cdot 10^5$$$).
Следующие $$$n$$$ строк содержат по два целых числа $$$p_i$$$ и $$$h_i$$$ — уровень крепости и высоту $$$i$$$-го снизу кружки слоя кофе ($$$1 \le p_i, h_i \le 10^9$$$). Гарантируется, что сумма $$$p_i \cdot h_i$$$ по всем $$$i$$$ не превосходит $$$10^{18}$$$.
В $$$i$$$-й из следующих $$$q$$$ строк дано единственное целое число $$$t_i$$$, определяющее $$$i$$$-й запрос ($$$1 \le t_i \le 10^9$$$).
Выведите $$$q$$$ строк, в $$$i$$$-й из которых содержится единственное целое число от $$$0$$$ до $$$n$$$ — ответ $$$i$$$-й запрос. Если для какого-то запроса ответ такой, что нельзя добиться требуемого уровня крепости, выведите в качестве ответа на этот запрос число $$$-1$$$.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены. Обратите внимание, что прохождение тестов из условия не является необходимым для тестирования на некоторых группах тестов.
Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке | |
0 | – | примеры из условия | полная | ||
1 | 5 | $$$q \le 100$$$; $$$n \le 15$$$; $$$p_i, h_i \le 100$$$ | 0 | полная | |
2 | 5 | $$$n, q \le 500$$$ | 0, 1 | первая ошибка | |
3 | 7 | $$$n, q \le 2000$$$ | 0 – 2 | первая ошибка | |
4 | 8 | $$$n, q \le 5000$$$ | 0 – 3 | первая ошибка | |
5 | 15 | $$$p_i \le p_j$$$ для $$$i | lt; j$$$ | первая ошибка | |
6 | 10 | $$$h_i = h_j$$$ для любых $$$i, j$$$; есть не более двух различных $$$p_i$$$ | первая ошибка | ||
7 | 10 | $$$h_i = h_j$$$ для любых $$$i, j$$$ | 6 | первая ошибка | |
8 | 15 | $$$p_i \le 10^5$$$ | 0, 1 | первая ошибка | |
9 | 25 | без дополнительных ограничений | 0 – 8 | первая ошибка |
3 41 13 72 41234
2 2 3 -1
Для примера из условия: