2차원 평면의 KOI마을에 N개의 집이 있다. 각 i번째 집의 위치는 (X_i, Y_i)이다.

i번째 집과 j번째 집 사이의 거리는 |X_i-X_j| + |Y_i-Y_j| 이다. 즉, 두 집 사이의 거리는 X의 차이와 Y의 차이의 합이다.

예를 들어, (1,6)에 위치한 점과 (2,4)에 위치한 집은 (2-1)+(6-4)인 3만큼 떨어져 있다.

KOI 마을은 재난 발생시 주민들이 안전하게 대피할 수 있도록 K개의 집에 대피소를 설치할 계획이다.

모든 주민의 안전을 고려하여, 집에서 가장 가까운 대피소를 이동할 때 가장 긴 거리가 최소가 되도록 대피소를 설치할 K개의 집을 선택하고, 그 때, 대피소와 가장 멀리 떨어진 집과의 거리를 구하려고 한다.

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

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

하지만 (3, 3)와 (6, 12)에 위치한 집에 대피소를 설치하면 가장 가까운 대피소와 가장 멀리 떨어져 있는 집은

(8, 9)에 위치한 집으로, (6, 12)와 5만큼 떨어져 있다.

대피소를 어떻게 설치해도 최대 거리가 5보다 작아지는 경우가 없으므로 5가 구하고자 하는 거리가 된다.

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

대피소 timer 3s memory 1024MB

대피소 3s 1024MB