대피소

문제

$22$차원 평면의 KOI 마을에 $NN$개의 집이 있다. 각 $ii$번째 집의 위치는 $(X_i,Y_i)(X\_i\; ,\; Y\_i)$이다.

$ii$번째 집과 $jj$번째 집 사이의 거리는 $\mathrm{\mid }{X}_i-X_j\mathrm{\mid }+\mathrm{\mid }{Y}_i-Y_j\mathrm{\mid }|X\_i\; -\; X\_j\; |\; +\; |Y\_i\; -\; Y\_j\; |$이다. 즉, 두 집 사이의 거리는 $XX$의 차이와 $YY$의 차이의 합이다. 예를 들어, $(1,6)(1,\; 6)$에 위치한 집과 $(2,4)(2,\; 4)$에 위치한 집은 $(2-1)+(6-4)(2\; -\; 1)\; +\; (6\; -\; 4)$인 $33$만큼 떨어져 있다.

KOI 마을은 재난 발생 시 주민들이 안전하게 대피할 수 있도록 $KK$개의 집에 대피소를 설치할 계획이다. 모 든 주민의 안전을 고려하여, 집에서 가장 가까운 대피소로 이동할 때 가장 긴 거리가 최소가 되도록 대피소를 설치할 $KK$개의 집을 선택하고, 그때 대피소와 가장 멀리 떨어진 집과의 거리를 구하려고 한다.

아래는 $55$개의 집이 각각 $(1,5)(1,\; 5)$, $(3,0)(3,\; 0)$, $(3,3)(3,\; 3)$, $(6,12)(6,\; 12)$, $(8,9)(8,\; 9)$에 위치한 마을의 예이다.

이 마을에 $22$개의 대피소를 설치하려고 한다. 만약 $(3,0)(3,\; 0)$과 $(1,5)(1,\; 5)$에 위치한 집에 대피소를 설치한다면 설치하지 않은 나머지 세 집에서 가까운 대피소까지의 거리가 각각 $33$, $1111$, $1212$이고, 이 중 가장 먼 거리는 $1212$이다.

하지만 $(3,3)(3,\; 3)$와 $(6,12)(6,\; 12)$에 위치한 집에 대피소를 설치하면 가장 가까운 대피소와 가장 멀리 떨어져 있는 집은 $(8,9)(8,\; 9)$에 위치한 집으로, $(6,12)(6,\; 12)$와 $55$만큼 떨어져 있다. 대피소를 어떻게 설치해도 최대 거리가 $55$보다 작아지는 경우가 없으므로 $55$가 구하고자 하는 거리가 된다.

KOI 마을의 집들의 위치와 설치할 대피소의 개수가 주어질 때, 대피소를 설치하는 모든 방법 중 가장 가까운 대피소와 집 사이의 거리 중 가장 큰 값이 가장 작을 때의 거리를 구해라.

입력

첫 번째 줄에 $NN$과 $KK$가 공백을 사이에 두고 주어진다.

다음 $NN$개의 줄에는 집의 위치가 주어지는데, 이 중 $ii$ (1 ≤ i ≤ N)번째 줄에는 $X_{i}X\_i$와 $Y_{i}Y\_i$가 공백을 사이에 두고 주어진다.

출력

첫 번째 줄에 답을 출력한다.

5 2
1 5
3 0
3 3
6 12
8 9

5

4 2
0 0
0 5
5 0
5 5

5

4 1
1 0
2 0
3 0
4 0

2

2 1
20 23
5 14

24