60031 대피소 Gold IV

문제

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

입력

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

다음 $N$개의 줄에는 집의 위치가 주어지는데, 이 중 $i$ ($1 ≤ i ≤ N$)번째 줄에는 $X_i$와 $Y_i$가 공백을 사이에 두고 주어진다.

출력

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

제한

• 주어지는 모든 수는 정수이다.
• $1 ≤ K ≤ 3$
• $K ≤ N ≤ 50$
• $0 ≤ X_i ≤ 100\,000$
• $0 ≤ Y_i ≤ 100\,000$
• 같은 위치에 집이 여럿 존재하지 않는다. 즉, $(X_1, Y_1)$, $(X_2, Y_2)$, $\cdots$, $(X_N , Y_N )$는 서로 다르다.

서브태스크

번호	배점	제한
1	5	$N = K + 1$
2	7	$K = 1$, 모든 $i$ ($1 ≤ i ≤ N$)에 대해 $X_i = i$이고 $Y_i = 0$이다.
3	10	$K = 1$
4	18	$K = 2$
5	35	$K = 3$, $1 ≤ i ≤ N - 1$에 대해 $X_i < X_{i+1}$이며, 모든 $i$ ($1 ≤ i ≤ N$)에 대해 $Y_i = 0$이다. 즉, $X$는 오름차순으로 정렬되어 있다.
6	25	$K = 3$

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