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$$$ 个粒子时可以产生的最大总能量。
示例
输入复制
33 367 06 17 11 0100 062 12 12 24 23 11 26 17 08 1
输出复制
67 100 6977 14
注意
在第一个测试用例中:
- 如果 Bessie 购买粒子 $$$4$$$,那么她最好只使用粒子 $$$1$$$ 并生成 $$$67$$$ 能量单位。
- 如果她购买粒子 $$$5$$$,那么她应该只使用粒子 $$$5$$$,它会生成 $$$100$$$ 能量单位。
- 如果她购买粒子 $$$6$$$,那么她应该使用粒子 $$$3$$$ 和 $$$6$$$,总共 $$$69$$$ 能量单位。