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 翻译