题目描述

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$ 个粒子时，她所能产生的最大能量总和。

样例

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

样例说明

在第一个测试用例中：

• 如果 Bessie 购买了粒子 $4$，最优策略是只用粒子 $1$ 来产生 $67$ 单位的能量。
• 如果她购买了粒子 $5$，则最佳选择是只用粒子 $5$，产生 $100$ 单位的能量。
• 如果她购买了粒子 $6$，则应选择粒子 $3$ 和 $6$，合计产生 $69$ 单位的能量。

由 ChatGPT 5 翻译

来源

Codeforces 2200F，英文题名 Mooclear Reactor 2。