2012

As we know,2012 is coming,and the presidents of many countries have planned to board the airships.We also know that every president i will bring a[i] bodyguards to make sure his safe,and he will pay b[i] billion dollars to U.N. We also know that some countries are more powerful than others,so if we have chose some countries to board the ship,we must make the powerful countries board first,and make sure that the bodyguards stay the same ship with his president.
Now,U.N has m ships. And every ship can only contain k people.So cannot hold all the people,but the U.N want to make more mongey .Make the most money for the U.N,then the U.N will give Lazy Yangyang a chance to survive when 2012 is coming.
Lazy Yangyang want to be safe so that he can inherit the job of ACM for the new world.To make the dream come true,the acmers of the world are solving the problem for Lady YY,and you are one of them………

In the first line there is an integer T, indicates the number of test cases. (T <= 10)
In each case, the first line contains three integers n,m and k. (0 <m<=n <=100,0<k<100000)
Then n line,every line has two integers a[i]、b[i], (0<=a[i]<100000,0<=b[i]<100)representing the bodyguards and dollars, ordered by their power,The first country is the most powerful country.

Most money that U.N can get.

1
4 2 400
60 1
180 1
180 1
260 1

3

You can choose country 1 3 4,make the 1 3 at ship 1,and make country 4 at ship 2;but you cannot make 1 4 at ship 1, and country 2 3 at ship 2,
because 2 is more powerful than country 4, so 2 should sit behind country 1!

alpc72

2010 ACM-ICPC Multi-University Training Contest（16）——Host by NUDT