조직 구성

어느 회사에 직원 $N$명이 있고, 이들을 비어 있지 않은 $k$개의 팀으로 나눈다. 이 회사는 무엇이든 수치로 관리한다.

• 직원 $a$는 검사를 두 번 받았고, 그 결과로 두 수 $x_a$와 $y_a$를 얻었다.
• 직원 $a$와 $b$의 차이는 $D(a, b) = |x_a - x_b| + |y_a - y_b|$이다.
• 회사의 조직력 지수 $SI$는 서로 다른 팀에 속한 두 직원 $a$, $b$에 대한 $D(a, b)$의 최솟값이다.

내년에도 팀 수는 $k$로 유지하지만, 조직력 지수가 가장 커지도록 직원을 다시 배치한다. 비어 있지 않은 $k$개의 팀으로 나눌 때 얻을 수 있는 조직력 지수의 최댓값을 구하라.

첫 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 10$)

각 테스트 케이스의 첫 줄에는 직원 수 $N$과 팀 수 $k$가 공백 하나로 구분되어 주어진다. ($2 \le k \le 10$, $k \le N \le 1000$)

이어지는 $N$개의 줄에는 직원 한 명의 검사 결과 $x$와 $y$가 공백 하나로 구분되어 주어진다. ($0 \le x, y \le 100\,000$)

각 테스트 케이스마다 얻을 수 있는 조직력 지수의 최댓값을 한 줄에 하나씩 출력한다.

직원이 $(0, 0)$, $(2, 2)$, $(3, 2)$ 세 명이고 $k = 2$라면, 두 팀 모두 비어 있으면 안 되므로 나누는 방법은 세 가지다. $\{(0,0)\}$과 $\{(2,2), (3,2)\}$로 나누면 $SI = \min\{4, 5\} = 4$이고, $\{(0,0), (2,2)\}$와 $\{(3,2)\}$로 나누면 $SI = \min\{5, 1\} = 1$이며, $\{(0,0), (3,2)\}$와 $\{(2,2)\}$로 나누면 $SI = \min\{5, 1\} = 1$이다. 따라서 최댓값은 $4$이다.

직원이 $(0,1)$, $(0,0)$, $(1,0)$, $(2,2)$, $(2,3)$, $(3,2)$ 여섯 명이고 $k = 2$라면 나누는 방법이 31가지인데, $\{(0,1), (0,0), (1,0)\}$과 $\{(2,2), (2,3), (3,2)\}$로 나눌 때 $SI$가 $3$으로 가장 크다. 이 값은 $D((0,1), (2,2))$와 $D((1,0), (2,2))$에서 나온다.