Description

顺利打开游戏的某闯，刚刚戴上耳机就有一股强大的电流将其电晕。苏醒后，某闯意外的发现自己进入了游戏中的世界。这时游戏里的神明找到了他，并跟他说：“欢迎你来到这个世界，我的勇者。我将引导你完成你的使命。现在我可以为你提供N件生存物资。但是你不能贪心，你只能拿K件。我可以给你一个无限包裹用来装这些物资。但是你要注意，包裹是无限容量的，但是包裹开口的大小是固定的。只有直径不大于包裹开口直径的物资才能装得下”。在这里一时刻，某闯成功变身为勇者闯。

之后神明给出N件物资，每件物资都有自己的价值w和直径v。勇者闯可以选择K件合适的物品装进包裹里。他想尽可能的让自己拿到的物资总价值最大。请你帮助他计算出他所能得到的物资的最大总价值。

Input Format

第一行输入一个数T代表测试样例数（1≤T≤100）。

对于每组测试样例：

输入N+1行

第一行输入三个整数N(0≤N≤10^3)，M(1≤M≤10^9)，K(0≤K≤N) ，分别表示物资的数量，包裹的直径和勇者闯可以带走的物资的数量；

接下来N行，每行输入两个整数w、v，(1≤w、v≤10^9)。表示物资的价值和直径。

Output Format

对于每组样例：

输出一行，该行包含一个整数，表示勇者闯所获得的物资的最大总价值.

2
4 5 2
1 9
2 4
5 5
3 7
4 100 1
1 99
99 23
1001 10
32 44

7
1001

Source

1816 Online Judge 10.100.0.232