题目描述

你带着一些来之不易的金币来到了 Ye Olde 魔法商店，想要购买一些妙不可言的魔术物品。商店里有 $n$ 个魔术实体，每个实体都锁在一个特殊的魔术宝箱中。第 $i$ 个宝箱（和其中的实体）的售价为 $c_i$个金币，而其中实体的价值相当于 $v_i$ 个金币。你作为曾经完整钻研了《Ye Olde 魔法目录》的顶级做题家，当然毫无疑问地记住了每个盒子和其中实体的售价和价值。

然而像你这样的凡人，只能安全地携带一件魔法实体。因此，你想要得到最宝贵的一个。你本可以直接得到它的——如果不是因为调皮而又神奇的小恶魔的话。

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

小恶魔拥的魔力最多可以用来使用 $k$ 次魔法。当然，他可以不用完这 $k$ 次魔法，而你也可以随时空手走开（尽管这是一个奇耻大辱）。但是，如果你成功地买到了到一个实体（而没有被变成灰尘），则你必须保留该实体并离开商店。

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

输入格式

多组数据，第一行一个整数 $T$ 表示数据组数。

每组数据的第一行包括两个数 $n$ 和 $k$，分别表示魔术实体个数和小恶魔使用魔法的最大次数。 接下来 $n$ 行，第 $i$ 行包括两个数 $v_i$ 和 $c_i$，意义如【题目描述】所述。同一行的数用空格隔开。

输出格式

共 $T$ 行，每行一个整数表示答案。

1
3 1
10 5
8 1
20 12

7

数据范围

对于 $100\%$ 的数据，$1\le n\le 1.5×10^5,0\le k\le 9,0\le v_i,c_i\le 10^6$。