CF2200F.Mooclear Reactor 2

Bessie needs to produce energy as possible in her mooclear reactor. She has $n$ different particles.

Each particle is defined by two integers $x$ and $y$. The particle generates $x$ units of energy but has a reactivity $y$, meaning that it can only exist together with at most $y$ other particles in the reactor. Formally, if this particle is chosen to generate energy, then at most $y$ particles (other than itself) can also be chosen to generate energy.

Bessie must choose a subset of particles that satisfy this constraint to generate energy. The amount of energy that she generates is equal to the sum of the energies of the particles in the subset.

There is a shop with $m$ particles. Bessie can buy exactly one particle from the shop. For each particle in the shop, determine the maximum total energy that Bessie would be able to produce if she were to buy only that particle from the shop. Bessie is not required to use the particle that is purchased from the shop.

贝茜需要在她的“牛核”反应堆中尽可能多地产生能量。她拥有 $n$ 种不同的粒子。

每种粒子由两个整数 $x$ 和 $y$ 定义：该粒子可产生 $x$ 单位能量，但其反应活性为 $y$，意味着它最多只能与 $y$ 个其他粒子共存于反应堆中。形式化地说，若选择该粒子来产生能量，则至多还能再选择 $y$ 个（除自身外的）粒子来产生能量。

贝茜必须选择一个满足上述约束的粒子子集来产生能量。她所生成的总能量等于该子集中所有粒子的能量之和。

现有一家商店，其中出售 $m$ 种粒子。贝茜恰好可以从该商店购买一种粒子。对商店中的每种粒子，请计算：若贝茜仅购买该粒子（即从商店中只购入这一种粒子），则她所能产生的最大总能量是多少？注意：贝茜并非必须使用从商店中购买的粒子。

The first line contains a single integer $t$ ($1 \leq t \leq 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $m$ ($1 \leq n, m \leq 2 \cdot 10^5$) — the number of particles that Bessie has and the number of particles in the shop, respectively.

The $i$-th of the next $n$ lines contains two integers $x$ and $y$ ($1 \leq x \leq 10^9$, $0 \leq y \leq n$) — the energy and reactivity of Bessie's $i$-th particle.

The $j$-th of the next $m$ lines contains two integers $x$ and $y$ ($1 \leq x \leq 10^9$, $0 \leq y \leq n$) — the energy and reactivity of the shop's $j$-th particle.

It is guaranteed that the sum of $n$ over all test cases and the sum of $m$ over all test cases do not exceed $2 \cdot 10^5$.

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

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n, m \leq 2 \cdot 10^5$）——分别表示贝茜拥有的粒子数量以及商店中粒子的数量。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $x$ 和 $y$（$1 \leq x \leq 10^9$，$0 \leq y \leq n$）——表示贝茜的第 $i$ 个粒子的能量和反应性。

再接下来的 $m$ 行中，第 $j$ 行包含两个整数 $x$ 和 $y$（$1 \leq x \leq 10^9$，$0 \leq y \leq n$）——表示商店中第 $j$ 个粒子的能量和反应性。

保证所有测试用例的 $n$ 之和与所有测试用例的 $m$ 之和均不超过 $2 \cdot 10^5$。

For each test case, print $m$ integers. The $i$-th integer should be the maximum total energy that Bessie can produce if she purchases the $i$-th particle from the shop.

对于每个测试用例，输出 $m$ 个整数。其中第 $i$ 个整数表示：如果贝茜从商店购买第 $i$ 个粒子，她所能产生的最大总能量。

In the first test case:

• If Bessie buys particle $4$, then it is optimal for her to only use particle $1$ and generate $67$ energy units.
• If she buys particle $5$, then she should only use particle $5$, which generates $100$ energy units.
• If she buys particle $6$, then she should use particles $3$ and $6$, for a total of $69$ energy units.

在第一个测试用例中：

• 如果贝茜购买粒子 $4$，那么她只使用粒子 $1$ 是最优的，可产生 $67$ 单位能量。
• 如果她购买粒子 $5$，那么她应仅使用粒子 $5$，可产生 $100$ 单位能量。
• 如果她购买粒子 $6$，那么她应使用粒子 $3$ 和粒子 $6$，总共产生 $69$ 单位能量。