A16861 · Mooclear Reactor 2

题目描述

Bessie 需要在她的“mooclear”反应堆中尽可能多地产生能量。她有 $n$ 种不同的粒子。 每个粒子由两个整数 $x$ 和 $y$ 定义。该粒子可以产生 $x$ 单位的能量，但具有反应性 $y$，意味着该粒子只能与至多 $y$ 个其它粒子一起存在于反应堆中。形式化来说，如果选择这个粒子来产生能量，那么最多只能再选择 $y$ 个其它粒子（不包括自身）参与产生能量。 Bessie 必须选择一些满足上述限制的粒子子集来产生能量。她所能产生的能量总量等于被选择粒子的能量之和。 有一个商店提供 $m$ 个粒子。Bessie 可以从商店中恰好购买一个粒子。对于商店里的每一个粒子，请你求出如果她只买这个粒子，那么她最多能产生的能量是多少。Bessie 并不要求一定要用上购买的粒子。

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 2 \cdot 10^5$），分别表示 Bessie 拥有的粒子数和商店中的粒子数。 接下来的 $n$ 行，每行包含两个整数 $x$ 和 $y$（$1 \leq x \leq 10^9$，$0 \leq y \leq n$），分别表示 Bessie 的第 $i$ 个粒子的能量和反应性。 接下来的 $m$ 行，每行包含两个整数 $x$ 和 $y$（$1 \leq x \leq 10^9$，$0 \leq y \leq n$），分别表示商店中第 $j$ 个粒子的能量和反应性。 保证所有测试用例中 $n$ 的总和以及 $m$ 的总和均不超过 $2 \cdot 10^5$。

每组测试用例输出 $m$ 个整数，第 $i$ 个整数表示 Bessie 购买商店中第 $i$ 个粒子时，她所能产生的最大能量总和。

输入 #1

输出 #1

67 100 69
7
7 14