28574번 - Активная подготовка к битве 다국어

Карнаж хочет сразиться с Веномом, но для этого ему нужно набрать силы. Он узнал, что поедание некоторых людей положительно влияет на способности симбиотов, и чем сильнее и способнее был человек, тем полезнее будет его съесть. Однако люди имеют неприятное свойство сопротивляться, и если человек достаточно проворен, то он может успеть поднять шум прежде, чем с ним будет покончено, что привлечёт внимание полиции и детектива Патрика Маллигана.

Сейчас сила Карнажа $P$ равна 1, а полиция ничего не подозревает, и их уровень настороженности $C$ равен 0. Карнаж может добраться до $n$ людей, $i$-го из которых можно описать парой чисел $(p_i, c_i)$. При попытке съесть $i$-го человека может случиться одно из двух:

• Если $P \geqslant p_i$, то Карнаж достаточно силен, чтобы разделаться с жертвой без шума и увеличить свою силу на $p_i$, не поднимая уровень настороженности полиции;
• Иначе, человек все равно будет съеден (и сила Карнажа $P$ увеличится на $p_i$), но и настороженность полиции возрастёт на $c_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$, а иначе --- минимальному вниманию полиции к Карнажу после того, как он наберет эту силу.