P4765 [CERC2014] The Imp

你带着一些来之不易的金币来到了 Ye Olde 魔法商店，想要购买一些妙不可言的魔术物品。商店里有 $n$ 个魔术实体，每个实体都锁在一个特殊的魔术宝箱中。第 $i$ 个宝箱（和其中的实体）的售价为 $c_i$个金币，而其中实体的价值相当于 $v_i$ 个金币。你作为曾经完整钻研了《Ye Olde 魔法目录》的顶级做题家，当然毫无疑问地记住了每个盒子和其中实体的售价和价值。 然而像你这样的凡人，只能安全地携带一件魔法实体。因此，你想要得到最宝贵的一个。你本可以直接得到它的——如果不是因为调皮而又神奇的小恶魔的话。 小恶魔可以使用魔法，从而将某一个魔术宝箱内的实体转化为毫无价值的灰尘。当然，他会在你购买一个魔术宝箱后立即对其使用该魔法，这样你就为这个宝箱付了钱而没能得到里面的实体。因此，你被迫另买一个，再买一个…… 小恶魔拥的魔力最多可以用来使用 $k$ 次魔法。当然，他可以不用完这 $k$ 次魔法，而你也可以随时空手走开（尽管这是一个奇耻大辱）。但是，如果你成功地买到了到一个实体（而没有被变成灰尘），则你必须保留该实体并离开商店。 你的目标是最大化你的收益（所购实体的价值减去支付的所有费用（包括购买当前实体和之前的灰尘）），而小恶魔则希望将其最小化。如果你和小恶魔都使用最佳策略，那么你的收益将会相当于多少金币？

**本题每个测试点包含多组数据。** 第一行包含一个正整数 $T$ 表示测试数据组数。 每组数据的第一行包括两个数 $n$ 和 $k$ ，分别表示魔术实体个数和小恶魔使用魔法的最大次数。 接下来 $n$ 行，每行包括两个数 $v_i$ 和 $c_i$，分别表示第 $i$ 个盒子和其中实体的价值和售价。

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

$1\le n\le1.5\times10^5,0\le k\le9,0\le v_i,c_i\le10^6$。