Abhijeet and rectangles

All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Problem description
Abhijeet loves to play with rectangles. Today he has N rectangles of various sizes with him. He started to arrange them on the coordinate plane such that the area of intersection is maximized. However, he never rotated the rectangles he had, he only moved them here and there.
Abhijeet soon realized that the game was boring and decided to introduce a modification. He decided to remove atmost M of those rectangles and arrange others on coordinate plane such that the area of intersection is maximized.
Given the dimensions of N rectangles and M, can you answer maximum possible area of intersection with above rules?
Note: If all the rectangles are removed, the area of intersection is considered as 0.
Input
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.First line of each test case has two integer N and M. N lines follow, each has two integers representing the length and breadth of the rectangle.
Output
For each test case, output a single line containing the required answer.
Constraints
 1 ≤ T ≤ 10^{5}
 1 ≤ N ≤ 10^{5}
 0 ≤ M ≤ N
 1 ≤ Rectangle Dimensions ≤ 10^{9}
 1 ≤ Sum of N over all test cases ≤ 10^{6}
Example
Input: 3 1 1 10 10 2 0 5 10 5 5 2 1 1 1 2 2 Output: 100 25 4
Explanation
Example case 1Abhijeet has only one rectangle. He can remove it, but then the area will be 0. Optimal way is not to remove it. Area = 10 * 10 = 100
Example case 2Abhijeet cannot remove any rectangles in this case. He can however, place them such that the smaller 5 by 5 rectangle is completely inside the larger 5 by 10 rectangle. Then the area of intersection is 5 * 5 = 25
Example case 3Abhijeet can remove atmost 1 rectangles in this case. He can remove the smaller rectangle of size 1 by 1. He is then left with 2 by 2 rectangle of area 4.
Author:  anudeep2011 
Tester:  xiaodao 
Editorial  http://discuss.codechef.com/problems/ANUAHR 
Tags  anudeep2011, cook54, datastructure, medium 
Date Added:  15012015 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions