球与箱

时间限制：2s
空间限制：1024MB

题目描述

球先生拥有 $M$ 种球，每种数量都足够多；箱先生拥有足够多的钱。另有 $N$ 个箱子，第 $i$ 个箱子容量为 $V_i$，价格为 $P_i$，箱先生可在游戏中的任意时刻购买箱子。

游戏反复进行：球先生选择一种球交给箱先生；箱先生可以拒收并结束游戏，或接收后把球放进一个已购买的箱子。若该箱内球数不超过容量且所有球同种，箱先生获得 1 元，否则游戏立刻结束。球先生希望箱先生最终的钱尽量少，箱先生希望尽量多；双方都知道全部信息。求最优策略下箱先生相对初始资金增加了多少。每个输入含多组测试数据。

输入格式

T
N M
V_1 P_1
...
V_N P_N

输出格式

对每组测试数据输出一行答案。

样例输入 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

数据范围

• $1\le T,N,M\le3\times10^5$；
• $1\le V_i,P_i\le10^9$；
• 所有测试数据中 $N$ 的总和不超过 $3\times10^5$；