F. Mooclear Reactor 2
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Бесси нужно произвести как можно больше энергии в своем реакторе mooclear. У нее есть $$$n$$$ различных частиц.

Каждая частица определяется двумя целыми числами $$$x$$$ и $$$y$$$. Частица генерирует $$$x$$$ единиц энергии, но имеет реактивность $$$y$$$, что означает, что она может существовать вместе не более чем с $$$y$$$ другими частицами в реакторе. Формально, если эта частица выбрана для генерации энергии, то не более чем $$$y$$$ частиц (кроме самой себя) также могут быть выбраны для генерации энергии.

Бесси должна выбрать подмножество частиц, которое удовлетворяет этому ограничению, чтобы генерировать энергию. Количество энергии, которую она генерирует, равно сумме энергий частиц в подмножестве.

В магазине есть $$$m$$$ частиц. Бесси может купить ровно одну частицу из магазина. Для каждой частицы в магазине определите максимальную общую энергию, которую Бесси сможет произвести, если она купит только эту частицу из магазина. Бесси не обязана использовать частицу, купленную в магазине.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$) — количество частиц, которые есть у Бесси, и количество частиц в магазине соответственно.

$$$i$$$-я из следующих $$$n$$$ строк содержит два целых числа $$$x$$$ и $$$y$$$ ($$$1 \leq x \leq 10^9$$$, $$$0 \leq y \leq n$$$) — энергия и реактивность $$$i$$$-й частицы Бесси.

$$$j$$$-я из следующих $$$m$$$ строк содержит два целых числа $$$x$$$ и $$$y$$$ ($$$1 \leq x \leq 10^9$$$, $$$0 \leq y \leq n$$$) — энергия и реактивность $$$j$$$-й частицы магазина.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных и сумма $$$m$$$ по всем наборам входных данных не превышают $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$m$$$ целых чисел. $$$i$$$-е целое число должно быть максимальной общей энергией, которую Бесси может произвести, если она покупает $$$i$$$-ю частицу из магазина.

Пример
Входные данные
3
3 3
67 0
6 1
7 1
1 0
100 0
62 1
2 1
2 2
4 2
3 1
1 2
6 1
7 0
8 1
Выходные данные
67 100 69
7
7 14
Примечание

В первом наборе входных данных:

  • Если Бесси купит частицу $$$4$$$, то ей оптимально использовать только частицу $$$1$$$ и сгенерировать $$$67$$$ единиц энергии.
  • Если она купит частицу $$$5$$$, то ей следует использовать только частицу $$$5$$$, которая генерирует $$$100$$$ единиц энергии.
  • Если она купит частицу $$$6$$$, то ей следует использовать частицы $$$3$$$ и $$$6$$$, в сумме $$$69$$$ единиц энергии.