PCB

인쇄 회로 기판(printed circuit board, 줄여서 PCB)은 비전도성 기판 위에 얇게 입힌 구리를 깎아 만든 도체 경로(배선)로 전자 부품들을 전기적으로 연결하는 부품이다. PCB는 개인용 컴퓨터의 메인보드, 그래픽 카드, RAM 등 어디에서나 볼 수 있다. 여러 가지 이유로 PCB는 부품들을 되도록 짧고 효율적으로 연결해야 하므로, 각 부품을 어떻게 배선할지가 PCB 설계의 핵심 문제이다.

주문을 받아 PCB를 제작하는 한 회사가 차세대 스마트 기기에 들어갈 PCB(모델명 iCPC-2012)의 설계를 의뢰받았다. 명세에 따르면 이 기판에는 부품 $C_1, \dots, C_N$ 총 $N$개와, 클록(clock)이라 부르는 특수 부품 두 개가 있다. 한 클록은 자신에게 연결된 최대 $K$개의 부품에 주기적으로 신호를 보낼 수 있다(즉, 한 클록은 최대 $K$개의 부품을 담당한다). 여기서 $K \ge N/2$이다. 모든 부품은 동작 중 동기화되어야 하므로 각 부품 $C_i$는 두 클록 중 정확히 하나에 연결되어야 한다. 두 클록은 서로 완벽히 동기화되어 있다고 가정한다.

기판의 모양과 $N$개 부품의 위치는 이미 정해졌지만, 두 클록을 어디에 둘지는 아직 정하지 않았다. 부품 간 동기화를 위해, 각 부품에서 연결된 클록까지 이어지는 경로 중 가장 긴 것의 길이를 최소로 만들고자 한다. 두 클록을 가장 알맞은 위치에 두었을 때, 이 "가장 긴 경로"의 최소 길이를 구하는 프로그램을 작성하라.

iCPC-2012는 다음 성질을 가진다.

1. 부품과 클록을 잇는 모든 경로는 수평 또는 수직 선분으로만 이루어진다.
2. 모든 경로는 부품 아래를 지나므로, 서로 겹침을 신경 쓰지 않고 되도록 짧게 자유로이 설계할 수 있다.
3. 각 부품 $C_i$의 위치 $p_i = (x_i, y_i)$는 두 짝수의 쌍으로 주어진다.
4. 각 클록은 $-10^6 \le x, y \le 10^6$을 만족하는 임의의 위치 $(x, y)$에 둘 수 있으며, 어떤 부품 $C_i$와 같은 위치에 두어도 된다.

성질 (1)과 (2)에 의해, 부품에서 클록까지 경로의 길이는 잇는 방식이 아니라 오로지 두 점의 좌표로만 정해진다. 즉 그 길이는 두 위치의 수평 거리와 수직 거리의 합(맨해튼 거리)과 같다.

위 그림은 $N = 12$, $K = 7$인 예이다. 12개 부품의 위치 $p_i$는 작은 원으로, 두 클록의 최적 위치 중 하나는 검은 사각형으로 표시했다. 그림의 경로들은 (1), (2)를 만족하며 가장 긴 경로의 길이는 $7$로, 이것이 정답이다. 이러한 최적 배치가 유일하지는 않다.

입력은 표준 입력으로 주어진다. 입력은 $T$개의 테스트 케이스로 이루어진다. 첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 각 테스트 케이스가 차례로 주어진다. 각 테스트 케이스의 첫 줄에는 두 정수 $N$과 $K$가 주어진다($2 \le N \le 100{,}000$, $N/2 \le K \le 100{,}000$). 그다음 $N$개의 줄에는 각 부품 $C_i$의 위치 $p_i = (x_i, y_i)$를 나타내는 두 짝수 $x_i$, $y_i$가 주어지며, 각 값은 $-1{,}000{,}000$ 이상 $1{,}000{,}000$ 이하이다. 한 줄의 두 정수는 공백 하나로 구분되고, 연속한 두 테스트 케이스 사이에 빈 줄은 없다.

각 테스트 케이스마다 표준 출력으로 정확히 한 줄을 출력한다. 그 줄에는 "가장 긴 경로"의 최소 가능 길이를 반올림한 정수 하나를 출력한다. 예를 들어 계산 결과가 $5.52$이면 $6$을, $5.49$이면 $5$를 출력한다. (모든 좌표가 짝수이므로 이 최소 길이는 항상 정수이다.)