Organization

A company has $N$ employees and splits them into $k$ nonempty teams. The company turns everything into numbers.

• Employee $a$ took two tests and got two values $x_a$ and $y_a$.
• The difference between employees $a$ and $b$ is $D(a, b) = |x_a - x_b| + |y_a - y_b|$.
• The strength index $SI$ of the company is the smallest $D(a, b)$ over all pairs of employees $a$, $b$ that sit in different teams.

Next year the company keeps $k$ teams and rearranges the employees so that the strength index is as large as possible. Compute the largest strength index that $k$ nonempty teams can reach.

The first line contains the number of test cases $T$. ($1 \le T \le 10$)

The first line of each test case contains the number of employees $N$ and the number of teams $k$, separated by a single space. ($2 \le k \le 10$, $k \le N \le 1000$)

Each of the next $N$ lines contains the two test results $x$ and $y$ of one employee, separated by a single space. ($0 \le x, y \le 100\,000$)

For each test case, print the largest strength index on its own line.

Take the three employees $(0, 0)$, $(2, 2)$, $(3, 2)$ with $k = 2$. Neither team may be empty, so there are three ways to split them. $\{(0,0)\}$ with $\{(2,2), (3,2)\}$ gives $SI = \min\{4, 5\} = 4$, $\{(0,0), (2,2)\}$ with $\{(3,2)\}$ gives $SI = \min\{5, 1\} = 1$, and $\{(0,0), (3,2)\}$ with $\{(2,2)\}$ gives $SI = \min\{5, 1\} = 1$. The largest value is $4$.

Take the six employees $(0,1)$, $(0,0)$, $(1,0)$, $(2,2)$, $(2,3)$, $(3,2)$ with $k = 2$. There are 31 ways to split them, and $\{(0,1), (0,0), (1,0)\}$ with $\{(2,2), (2,3), (3,2)\}$ reaches the largest value $SI = 3$. That value comes from $D((0,1), (2,2))$ and from $D((1,0), (2,2))$.