[CERC2014] The Imp

## 题目描述 你带着一些来之不易的金币来到了 Ye Olde 魔法商店，想要购买一些妙不可言的魔术物品。商店里有 $n$ 个魔术实体，每个实体都锁在一个特殊的魔术宝箱中。第 $i$ 个宝箱（和其中的实体）的售价为 $c_i$个金币，而其中实体的价值相当于 $v_i$ 个金币。你作为曾经完整钻研了《Ye Olde 魔法目录》的顶级做题家，当然毫无疑问地记住了每个盒子和其中实体的售价和价值。 然而像你这样的凡人，只能安全地携带一件魔法实体。因此，你想要得到最宝贵的一个。你本可以直接得到它的——如果不是因为调皮而又神奇的小恶魔的话。 小恶魔可以使用魔法，从而将某一个魔术宝箱内的实体转化为毫无价值的灰尘。当然，他会在你购买一个魔术宝箱后立即对其使用该魔法，这样你就为这个宝箱付了钱而没能得到里面的实体。因此，你被迫另买一个，再买一个…… 小恶魔拥的魔力最多可以用来使用 $k$ 次魔法。当然，他可以不用完这 $k$ 次魔法，而你也可以随时空手走开（尽管这是一个奇耻大辱）。但是，如果你成功地买到了到一个实体（而没有被变成灰尘），则你必须保留该实体并离开商店。 你的目标是最大化你的收益（所购实体的价值减去支付的所有费用（包括购买当前实体和之前的灰尘）），而小恶魔则希望将其最小化。如果你和小恶魔都使用最佳策略，那么你的收益将会相当于多少金币？ ## 输入格式 **本题每个测试点包含多组数据。** 第一行包含一个正整数 $T$ 表示测试数据组数。 每组数据的第一行包括两个数 $n$ 和 $k$ ，分别表示魔术实体个数和小恶魔使用魔法的最大次数。 接下来 $n$ 行，第 $i$ 行包括两个数 $v_i$ 和 $c_i$，意义如【题目描述】所述。同一行的数用空格隔开。 ## 输出格式 对于每组数据，输出一行一个数表示答案。 ## 数据范围与提示 $1\le n\le1.5\times10^5,0\le k\le9,0\le v_i,c_i\le10^6$。

You arrive in 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 $c_i$ gold pieces to buy, and contains an item worth $v_i$ 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 minimize it. If both you and the creature use the optimal strategy, how much gold will you earn?

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 \le n \le 150 000)$ and the the maximum number of The Imp’s spells $k(0 \le k \le 9)$. The next $n$ lines contain the items’values and costs, the $i-th$ line containing the numbers $v_i$ and $c_i$, in that order $(0 \le v_i, c_i \le 10^6)$.

For each test case, output one line containing your gain.

1
3 1
10 5
8 1
20 12

7