Today Alex and Frank are playing a famous game named "Overplay Your Hand".
There are N boxes each containing different gifts .The cost price and selling price of ith box is and respectively.
Alex starts the game by purchasing a particular box. According to the game rules Frank can reduce the selling price of the box that Alex purchases, to 0 ( Thereby wasting Alex's money ). As the selling price of the box is reduced to 0, it is waste and thereby forcing Alex to pick another box.
Alex can purchase at most 1 box whose selling price has not been reduced to 0 by Frank
Frank has at most R turns. He may refrain from using his turn(i.e does not reduce selling price to 0) thereby allowing Alex to take away the box and the game ends. But he would want to minimize Alex's total profit and Alex's aim is to maximize her total profit ( selling price of the box - all the previous expenditure in buying the boxes ).
Alex can quit the game without buying anything. ( Only when there is no chance of getting profit )
You need to help Alex and tell her the maximum profit she can earn when both Alex and Frank use the optimal strategy.
Note: Whenever Frank uses his turn, the selling price will reduce to 0 but the buying price will remain same so there is still cost incurred in buying the box ( previous expenditure )
Input Format :
The first line contains T, number of testcases.
The second line of input contains two integers N and R denoting the number of boxes and the maximum number of turns that Frank is allowed respectively.
N lines follow where ith line contains two integers G and D, denoting the Selling Price and the Cost price respectively of the ith box.
Output Format :
Output the maximum profit that Alex can earn if everyone plays optimally.
Constraints :
1 <= T <= 100
1 <= N <= 200000
0 <= R <= 10
0 <= G, D <= 10^7
Setter : Akshat Dua
1st Testcase:
Here cost price of all the boxes is same.
Suppose Alex selects 2nd last box (S.P. = 50, C.P. = 10)
Profit = 50-10 = 40
Since Frank plays optimally, therefore he will use his turn and reduce the S.P. to 0.
Now Alex is under loss of 10 dollars.
Since the game ends only when Alex buys a box whose selling price is not reduced to 0 by Frank or she can't find a way to have net positive profit ( in which case ans is 0 ), she will buy another box.
Obviously she will pick the box that maximizes her profit. In this case the last box ( S.P. = 60, C.P.= 10 ).
Profit = 60-10 =50
As Frank has no other turn left, Alex walks away with a net profit of (50-10) = 40.
Here 10 is the cost of purchasing previous box.
You can see that this is the maximum profit she can earn if both of them play optimally.
