Карнаж хочет сразиться с Веномом, но для этого ему нужно набрать силы. Он узнал, что поедание некоторых людей положительно влияет на способности симбиотов, и чем сильнее и способнее был человек, тем полезнее будет его съесть. Однако люди имеют неприятное свойство сопротивляться, и если человек достаточно проворен, то он может успеть поднять шум прежде, чем с ним будет покончено, что привлечёт внимание полиции и детектива Патрика Маллигана.
Сейчас сила Карнажа $$$P$$$ равна 1, а полиция ничего не подозревает, и их уровень настороженности $$$C$$$ равен 0. Карнаж может добраться до $$$n$$$ людей, $$$i$$$-го из которых можно описать парой чисел $$$(p_i, c_i)$$$. При попытке съесть $$$i$$$-го человека может случиться одно из двух:
Одновременно можно охотиться только на одну цель, и логично, что каждого человека можно съесть не более одного раза. Порядок, в котором он будет охотиться за жертвами, Карнаж выбирает сам.
На самом деле, Карнаж не знает, насколько опасен Веном, поэтому он делает $$$q$$$ предположений о силе противника: $$$i$$$-е предположение характеризуется потенциально возможной силой Венома $$$x_i$$$. Для каждого предположения найдите минимальную настороженность полиции, которая может получиться при наборе Карнажем силы $$$P \geqslant x_i$$$, или определите, что такую силу набрать невозможно.
Первая строка содержит два целых числа $$$n$$$ и $$$q$$$ — количество потенциальных жертв Карнажа и количество его предположений о силе Венома ($$$1 \leqslant n \leqslant 10^5$$$; $$$1 \leqslant q \leqslant 10^6$$$).
Следующие $$$n$$$ строк содержат описания людей: в $$$i$$$-й строке через пробел записаны два целых числа $$$p_i$$$ и $$$c_i$$$ — уровень силы $$$i$$$-го человека и потенциальный прирост внимания полиции при охоте на него ($$$1 \leqslant p_i \leqslant 10^9$$$; $$$1 \leqslant c_i \leqslant 10^9$$$).
Следующая строка содержит $$$q$$$ целых чисел $$$x_1, x_2, \ldots, x_q$$$, записанных через пробел. Число $$$x_i$$$ описывает $$$i$$$-е предположение Карнажа о силе Венома ($$$1 \leqslant x_i \leqslant 10^9$$$). Память иногда подводит Карнажа, поэтому одно и то же значение может встречаться в этой последовательности несколько раз.
Выведите через пробел $$$q$$$ чисел. Число номер $$$i$$$ должно описывать ответ для $$$i$$$-го предположения. Если невозможно набрать силу, не меньшую $$$x_i$$$, ответ равен $$$-1$$$, а иначе — минимальному вниманию полиции к Карнажу после того, как он наберет эту силу.
6 5 8 10 10 10 4 4 2 3 8 8 8 5 3 7 32 36 36
3 4 5 5 5
9 10 9 8 3 1 2 1 8 9 3 1 5 2 3 1 4 1 10 10 75 53 82 22 6 27 21 86 14 35
-1 -1 -1 1 1 1 1 -1 1 1