UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4047. [Cerc2014] The Imp

Statistics 下载数据

Description

You arrive m Ye Olde Magic Shoppe with some hard-earned gold to purchase wondrous and 
unique magic items. There are n such items in the shop, each of them locked in a special magic 
box. The i-th box costs ci gold pieces to buy, and contains an item worth vi gold pieces. The 
costs and item values are known to you, as you have previously read, mastered, and memorized 
Ye Olde Magic Catalogue. 
A mortal, such as you, can safely carry only one magic item. You therefore aim to get the 
most precious one. And obtain it you would, if not for a malicious, magical creature, known as 
The Imp. 
The Imp can cast a mischievous spell, which transforms the content of any magic box into 
worthless dust. Of course, he will use the spell just after you buy a box, to make you pay for the 
item and not get it. You are thus forced to buy another box, and then the next one_ 
The Imp has enough magic to cast the spell at most k times. He can, of course, refrain from 
using it, allowing you to keep an item. You can walk away at any time, empty-handed (though 
it would surely be a disgrace). However, if you get an item, you must keep it and leave the shop. 
You aim to maximize your gain (the value of the acquired item minus all the expenses paid 
previously), while The Imp wants to mimmize it. If both vou and the creature use the optimal 
strategy, how much gold will vou earn? 
T组询问。每组询问: 
第一行有两个数字N,K,表示有N个物体,接下来每个物体有2个描述权值Vi, Ci,表示该物体的价值和价格。
商家很坑,他有K次机会使得你买完物品之后就立马让你买的该物品消失(但已经付了钱),而商家的目标
则是使得你的净收入尽量低。你可以无限量买东西,但最后只能带走一件物品,不过当然想要使得净收入尽
量高。在双方皆采取最佳策略的情况下,你最多能得到多少钱?(当然,你也可以什么都不买) 

Input

The first line of input contains the number of test cases T. The descriptions of the test cases 
follow: 
Each test case starts with a line containing the number of items n (1《n≤ 150 000) and the 
the maximum number of The Imp's spells k (0≤ k < 9). The next n lines contain the items' 
values and costs, the i-th line containing the numbers vi and ci, in that order (0≤ vi, ci≤ 10^6). 

Output

For each test case, output one line containing your gain

Sample Input

1
3 1
10 5
8 1
20 12

Sample Output

7

Hint

Source