28215번 - 대피소 서브태스크

문제

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 )$는 서로 다르다.

서브태스크

힌트