魔法商店

题目描述

魔法商店中有 $N$ 个魔术实体，每个实体都被锁在一个魔法宝箱中。第 $i$ 个宝箱售价为 $C_i$ 个金币，而其中实体的价值为 $V_i$ 个金币。朱迪最多只能安全携带一个魔术实体，因此她的目标是买到一个实体并使收益最大化；收益定义为：得到的实体价值减去她支付过的所有费用。

然而店里有一个小恶魔。每当朱迪购买一个宝箱后，小恶魔都可以立刻施法，把这个宝箱中的实体变成毫无价值的灰尘。小恶魔总共最多可以使用 $K$ 次这种魔法，也可以提前停止不再使用。朱迪也可以随时空手离开，因此她的收益至少为 $0$。如果朱迪和小恶魔都采用最优策略，请你求出朱迪最终能获得的收益。

数据范围

• $1 \le T \le 30$
• $1 \le N \le 1.5 \times 10^5$
• $0 \le K \le 9$
• $0 \le V_i,C_i \le 10^6$

输入格式

从标准输入按以下格式读取数据：

$T$

$N$ $K$

$V_1$ $C_1$

$V_2$ $C_2$

$\vdots$

$V_N$ $C_N$

其中：

• 第一行输入一个正整数 $T$，表示测试数据组数。
• 对于每组数据，第一行输入两个整数 $N,K$，分别表示魔法宝箱数量和小恶魔最多使用魔法的次数。
• 接下来 $N$ 行，每行输入两个整数 $V_i,C_i$，分别表示第 $i$ 个实体的价值和对应宝箱的售价。

输出格式

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

样例

1
3 1
10 5
8 1
20 12

7

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

4
3