分数: 900 点
问题陈述
球先生和盒子先生将玩球和盒子的游戏。
最初,鲍尔先生有 10^{100} 每个球 M 不同的类型,盒子先生有 10^{100} 日元。 有 N 框,其中 i第一个盒子有容量 V_i 和成本 P_i 日元。游戏过程中,盒子先生可以随时购买任意盒子。
在本游戏中,重复以下操作直至游戏结束:
- 鲍尔先生选择一个球并将其交给盒子先生。
- Box先生要么接受球,要么在不接受球的情况下结束比赛。
- 如果盒子先生接受了球,他会选择他购买的一个盒子并将球放入其中。
- 如果有球的盒子满足以下条件,盒子先生将收到 1 日元。否则,游戏结束。
- 盒子中的球数不超过其容量。
- 盒子里的所有球都是同一类型。
Ball 先生将以最佳方式发挥,以最小化 Box 先生的最终资金,而 Box 先生将以最佳方式发挥,以使其最大化。 整个游戏过程中,盒子先生的钱会增加多少?
在这里,两个玩家都可以访问所有信息。特别是,球先生可以看到每个盒子的容量、价格和内容(球的类型和数量)。 另外,请注意,Box 先生的初始资金足够大,他永远不会用完钱来购买 Box。
解决 T 每个输入文件的测试用例。
约束
- 1\le T,N,M\le 3\times 10^5
- 1\le V_i,P_i \le 10^9
- 总和 N 超过 T 测试用例最多 3\times 10^5.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出,其中 \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
输出
打印当两个玩家都处于最佳状态时,Box 先生的最终资金和初始资金之间的差额。
示例输入 1
3 3 2 1 1000000000 3 1 3 1 1 300000 1000000000 1 10 4 22 5 26 45 72 21 47 39 97 2 75 35 82 24 17 46 32 22 28 67
示例输出 1
2 0 28
在第一个测试用例中,有两种类型的球和三个盒子。 让我们将这两种类型的球称为白球和黑球,并将 i第盒盒 i。 这是游戏如何进行的示例,其中金钱增加了 2 日元。
- 球先生选择并给出了一个白球。
- 盒子先生接受球,购买盒子 2 为 1 日元,并将白球放入其中。
- 盒子 2 包含 1 白球。这满足了条件,所以 Box 先生收到 1 日元。
- 球先生选择并给出了一个白球。
- 盒子先生接受球并将其放入盒子中 2.
- 盒子 2 包含 2 白球。这满足了条件,所以 Box 先生收到 1 日元。
- 球先生选择并给出了一个黑球。
- 盒子先生接受球,购买盒子 3 为 1 日元,并将黑球放入其中。
- 盒子 3 包含 1 黑球。这满足了条件,所以 Box 先生收到 1 日元。
- 球先生选择并给出了一个白球。
- 盒子先生接受球并将其放入盒子中 2.
- 盒子 2 包含 3 白球。这满足了条件,所以 Box 先生收到 1 日元。
- 球先生选择并给出了一个白球。
- Box先生选择不接受而结束游戏。
最后,盒子 2 包含 3 白球和盒子 3 包含 1 黑球。 盒子先生花了 2 日元并收到 4 日元,所以他的钱增加了 2 日元。
在第二个测试用例中,Ball 先生可以以阻止 Box 先生赚钱的方式进行游戏。