← 返回题目列表

Codeforces · 2200/F

F. Mooclear 反应堆 2

中文机器翻译题面 查看原题

Bessie 需要在她的 mooclear 反应堆中尽可能地产生能量。她有$$$n$$$不同的粒子。

每个粒子由两个整数 $$$x$$$ 和 $$$y$$$ 定义。该粒子产生$$$x$$$单位能量,但具有反应性$$$y$$$,这意味着它只能与反应器中的最多$$$y$$$其他粒子一起存在。形式上,如果选择这个粒子来产生能量,那么最多也可以选择 $$$y$$$ 个粒子(除了它自己)来产生能量。

Bessie 必须选择满足此约束的粒子子集来产生能量。她产生的能量等于子集中粒子能量的总和。

有一家商店,里面有 $$$m$$$ 颗粒。贝西可以买 正好一个 商店的颗粒。 对于商店中的每个粒子,确定如果 Bessie 仅从商店购买该粒子,她能够产生的最大总能量。贝西不需要使用从商店购买的颗粒。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 2 \cdot 10^5$$$) — 分别是 Bessie 拥有的粒子数量和商店中的粒子数量。

接下来的 $$$n$$$ 行的第 $$$i$$$ 包含两个整数 $$$x$$$ 和 $$$y$$$ ($$$1 \leq x \leq 10^9$$$, $$$0 \leq y \leq n$$$) — Bessie 第 $$$i$$$ 粒子的能量和反应性。

接下来的 $$$m$$$ 行的第 $$$j$$$ 包含两个整数 $$$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

注意

在第一个测试用例中:

  • 如果 Bessie 购买粒子 $$$4$$$,那么她最好只使用粒子 $$$1$$$ 并生成 $$$67$$$ 能量单位。
  • 如果她购买粒子 $$$5$$$,那么她应该只使用粒子 $$$5$$$,它会生成 $$$100$$$ 能量单位。
  • 如果她购买粒子 $$$6$$$,那么她应该使用粒子 $$$3$$$ 和 $$$6$$$,总共 $$$69$$$ 能量单位。