#P3681. Finding the Rectangle

Finding the Rectangle

Description

Given N point on the x-y coordinates, you are to find the rectangle of the smallest area which covers no less than M points. The coordinates of the four vertices must be integers and the sides must be parallel to the axes. If one point lies on the sides of the rectangle, it is not considered as being covered. 

Input

The first line of input is the number of test case.
The first line of each test case contains two integers, N and M (1 ≤ MN ≤ 200).
The next N line each contain two integers xi, yi (1 ≤ xi, yi ≤ 10,000) describing the points.
There is a blank line before each test case.

Output

For each test case output the smallest area in a separate line.

5

2 1 200 6 100 5

2 2 200 6 100 5

2 1 1 1 1 1

2 2 1 1 1 1

8 5 5 7 6 6 6 8 7 5 7 9 8 6 8 8 9 7

4
306
4
4
20

Source

POJ Founder Monthly Contest – 2008.07.27

, windy7926778

</p>