대피소

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

• 주어지는 모든 수는 정수이다.
• $1 \leq K \leq 3$
• $K \leq N \leq 50$
• $0 \leq X_i \leq 100\,000$
• $0 \leq Y_i \leq 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 \leq i \leq N$)에 대해 $X_i = i$이고 $Y_i = 0$이다.
3. (10점) $K = 1$
4. (18점) $K = 2$
5. (35점) $K = 3$, $1 \leq i \leq N-1$에 대해 $X_i < X_{i+1}$이며, 모든 $i$ ($1 \leq i \leq N$)에 대해 $Y_i = 0$이다. 즉, $X$는 오름차순으로 정렬되어 있다.
6. (25점) $K = 3$

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

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

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