Vector is a very useful mathematical tool. It sometimes makes all the calculations very easy. So I decided to teach my 7 year old son this amazing tool. Don’t be surprised, he is a very talented young child. He already understands coordinate, drawing line in grids etc. So when I say him to draw a vector (4, 3) from a point (2, 7) he draws a line from (2, 7) to (6, 10). One day I decided to teach him the concept of area too. I gave him N vectors and told him to draw any K distinct vectors among those N vectors one after one. And also told him that I will give him cake of the size of the area he can bind by the polyline and x-axis. Surprisingly my kid is yet to capture the concept of negative number. So I decided to give him non-negative vectors only, that is both the x and y components of the vector will be non-negative. If you are wondering what happened after that, let me show you what he had drawn. I gave him four vectors (3, 5), (0, 2), (2, 2) and (3, 0) and told him to draw 3 of them one after one. So he drew (2, 2), (3, 0) and (3, 5) in this order shown in the diagram above. (He first drew (2,2) vector from (0, 0) to (2, 2); then he drew (3, 0) from (2, 2) to (5, 2) and finally (3, 5) from (5, 2) to (8, 7)) These 3 vectors and x-axis bind area of 21.5. Is it the maximum? That is your task. Input First line of the test case contains a single positive integer T which is at most 110. Then there follows T test cases. First line of a test case contains two positive integers N and K (1 ≤ K ≤ N ≤ 50). Then N lines follow, each contains description of a 2D vector (x, y) (0 ≤ x, y ≤ 50). The meaning of N and K are given in the problem statement. Output For each test case print the test case number followed by the maximum area covered by the polyline. To avoid floating point calculation output twice of the maximum area. To be more clear, please follow the sample input output.
2/2 Sample Input 2 43 35 02 22 30 42 35 02 22 30 Sample Output Case 1: 81 Case 2: 45