2550: Stars

There are N (1 ≤ N ≤ 400) stars in the sky. And each of them has a unique coordinate (x, y) (1 ≤ x, y ≤ N). Please calculate the minimum area of the rectangle (the edges of the rectangle must be parallel to the X, Y axes) that can cover at least K (1 ≤ K ≤ N) stars. The stars on the borders of the rectangle should not be counted, and the length of each rectangle’s edge should be an integer.

Input may contain several test cases. The first line is a positive integer T (T ≤ 10), indicating the number of test cases below.

For each test cases, the first line contains two integers N, K, indicating the total number of the stars and the number of stars the rectangle should cover at least.

Each of the following N lines contains two integers x, y, indicating the coordinate of the stars.

For each test case, output the answer on a single line.

2
1 1
1 1
2 2
1 1
1 2

1
2