AT_arc186_c.[ARC186C] Ball and Box

球橋和箱木进行一个用球和箱子的游戏。

一开始，球橋有 $M$ 种不同的球，每种球各有 $10^{100}$ 个，箱木有 $10^{100}$ 日元。同时有 $N$ 个箱子，第 $i$ 个箱子的容量为 $V_i$，价格为 $P_i$ 日元。在游戏过程中，箱木可以随时购买任意箱子。

游戏过程中，以下操作会不断重复，直到游戏结束：

1. 球橋选择一种球，递给箱木。
2. 箱木可以选择接收这个球，或者拒绝接收并结束游戏。
3. 如果箱木接收了球，他需要从已购买的箱子中选择一个，将球放入该箱子。
4. 若放入球后的箱子满足以下条件，箱木获得 $1$ 日元，否则游戏结束：
   • 箱子中的球的数量不超过该箱子的容量。
   • 箱子中的所有球都是同一种类型。

球橋会采取使箱木最终所持金钱尽可能少的最优策略，反之，箱木会采取使自己最终所持金钱尽可能多的最优策略。请问，整个游戏过程中，箱木的所持金钱最多能增加多少？

注意，双方都能看到所有信息。特别地，球橋可以看到每个箱子的容量和价格，以及每个箱子里装了多少、哪种球。并且，箱木的初始资金足够多，不会因为钱不够而无法购买箱子。

对于每个输入文件，需要解答 $T$ 个测试用例。

输入以如下格式从标准输入给出。这里 $\mathrm{case}_i$ 表示第 $i$ 个测试用例。

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

每个测试用例格式如下：

$N$ $M$
$V_1$ $P_1$
$V_2$ $P_2$
$\vdots$
$V_N$ $P_N$

请输出在双方都采取最优策略时，箱木最终所持金钱与初始金钱的差值。

数据范围

• $1 \leq T, N, M \leq 3 \times 10^5$
• $1 \leq V_i, P_i \leq 10^9$
• 所有测试用例的 $N$ 之和不超过 $3 \times 10^5$
• 所有输入均为整数

样例解释 1

第一个测试用例有 $2$ 种球和 $3$ 个箱子。我们把两种球分别叫做白球和黑球，把第 $i$ 个箱子叫做箱 $i$。以下是箱木最终所持金钱增加 $2$ 日元的一个游戏过程示例：

1. 球橋选择白球递给箱木。
2. 箱木接收球，并以 $1$ 日元购买箱 $2$，将白球放入。
   • 箱 $2$ 里有 $1$ 个白球，满足条件，箱木获得 $1$ 日元。
3. 球橋选择白球递给箱木。
4. 箱木接收球，将白球放入箱 $2$。
   • 箱 $2$ 里有 $2$ 个白球，满足条件，箱木获得 $1$ 日元。
5. 球橋选择黑球递给箱木。
6. 箱木接收球，并以 $1$ 日元购买箱 $3$，将黑球放入。
   • 箱 $3$ 里有 $1$ 个黑球，满足条件，箱木获得 $1$ 日元。
7. 球橋选择白球递给箱木。
8. 箱木接收球，将白球放入箱 $2$。
   • 箱 $2$ 里有 $3$ 个白球，满足条件，箱木获得 $1$ 日元。
9. 球橋选择白球递给箱木。
10. 箱木选择不接收，游戏结束。

最终，箱 $2$ 里有 $3$ 个白球，箱 $3$ 里有 $1$ 个黑球。箱木总共花了 $2$ 日元，获得了 $4$ 日元，因此所持金钱增加了 $2$ 日元。

第二个测试用例中，球橋可以采取让箱木无法赚钱的策略。

由 ChatGPT 4.1 翻译