魔法商店

题目描述:

狐狸尼克陪兔警官朱迪寻找失踪的动物们，他们不幸被大先生( 黑帮头目小鼩鼱 )的手下北极熊抓走了，并关在一个魔法商店里。北极熊走的时候交代一句：“如果你们能在小恶魔的"关照"下，得到一个魔术实体，并取得最大化收益；那么大先生将会放你们回去，并提供给你们所需要的线索信息”。

魔法商店里摆设一些妙不可言的魔术物品。商店里有 N 个魔术实体，每个实体都锁在一个特殊的魔法宝箱中。第 i ( 1 ≤ i ≤ N ) 个魔法宝箱(和其中的实体)的售价为 Ci 个金币，而其中实体的价值相当于 Vi 个金币。幸好狐狸尼克早年曾经完整地钻研过<魔法目录>，聪明的他当然毫无疑问地记住了每个魔法宝箱的售价和其中实体价值。

然而像兔警官朱迪这样的凡人，只能安全地携带一个魔术实体。为了能从大先生这里得到线索信息，朱迪必须要得到最宝贵的一个魔术实体而且还要利益最大化。朱迪本可以很轻松就得到它的——如果不是因为那调皮而又神奇的小恶魔的话。

小恶魔可以使用魔法，从而将某一个魔法宝箱内的实体转化为毫无价值的灰尘。当然，它会在朱迪购买一个魔法宝箱后立即对其使用该魔法，这样朱迪就为这个宝箱付了钱而没能得到里面的实体。因此，朱迪被迫另买一个，再买一个……

小恶魔拥有的魔力最多可以用来使用 K 次魔法。当然，它可以不用完这 K 次魔法，让朱迪成功保留一个魔术实体。而朱迪也可以随时空手走开（ 换句话说就是朱迪的收益至少是 0 ）。但是，如果朱迪成功地买到了一个实体（而没有被变成灰尘），则朱迪必须保留该实体并可以顺利的离开商店。

朱迪的目标是最大化她的收益（所得实体的价值减去支付的所有费用（包括购买当前实体和之前被小恶魔变成灰尘的实体）），而小恶魔则希望将其最小化。如果朱迪和小恶魔都使用最佳策略，那么朱迪的收益将会是多少金币？ 

输入格式:

第一行包含一个正整数 T，表示测试数据组数。对于每组数据格式如下：

第一行包括两个整数 N 和 K，分别表示魔法宝箱(魔术实体)个数和小恶魔使用魔法的最大次数。

接下来 N 行，第 i 行包括两个整数 Vi 和 Ci，意义如上文所述。同一行的两个整数用一个空格隔开。 

输出格式:

输出共 T行，对于每组数据，输出一行一个整数表示答案。

数据范围:

对于100%的数据：1 ≤ T ≤ 30；1 ≤ N ≤ 1.5×105；0 ≤ K ≤ 9；0 ≤ Vi, Ci ≤ 106。

测试点编号 T N
1~2 T = 10 N ≤ 20
3 T = 30 N ≤ 20
4 T = 30 N ≤ 100
5 T = 30 N ≤ 1000
6 T = 30 N ≤ 10,000
7~8 T = 20 N ≤ 100,000
9~10 T = 15 N ≤ 1.5×105

样例输入:

样例1：
1
3 1
10 5
8 1
20 12


样例2：
2
6 1
8 4
15 10
17 6
15 13
3 0
3 2
6 2
10 4
15 10
17 6
15 13
9 3
3 2

样例输出:

样例1：
7

样例2：
4
3

提示:

【样例1解释】 朱迪的最优选择就是优先购买 2 号魔法宝箱，如果调皮的小恶魔使用它仅有的一次魔法将 2 号魔法宝箱内的实体变成毫无价值的灰尘，接下来朱迪可以成功购买 3 号魔法宝箱，并保留该魔术实体。此时的收益为 20-(12 + 1)=7 个金币；如果小恶魔不使用魔法的话，那么朱迪的收益为 8-1= 7 个金币。 

【样例2解释】 对于第 1 组数据：朱迪的最优选择就是购买 1 号魔法宝箱，并保留该魔术实体。聪明的小恶魔是不会使用它那仅有的一次魔法的。此时朱迪的收益为 8-4=4 个金币。 对于第 2 组数据：朱迪的最优选择就是优先购买 5 号魔法宝箱，小恶魔使用 1 次魔法将 5 号魔法宝箱内的实体变成毫无价值的灰尘，接下来朱迪就可以成功购买 1 号魔法宝箱，并保留该魔术实体。聪明的小恶魔虽然还有一次使用魔法的机会，但是它不会使用的。此时的收益为 10-(4+3)=3 个金币。 

时间限制: 1000ms
空间限制: 256MB

来源: 温州市计算机学会2023比赛