Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
Language:
Finding the Rectangle
Time Limit: 1000MSMemory Limit: 65536K
Total Submissions: 3377Accepted: 1021

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.

Sample Input

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

Sample Output

4
306
4
4
20

Source

[Submit]   [Go Back]   [Status]   [Discuss]

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator