대피소

문제

N개의 집이 2차원 좌표 위에 있다. K개의 대피소를 집이 있는 위치 중에서 설치하려 한다.

각 집은 가장 가까운 대피소로 이동하며, 거리는 맨해튼 거리(|x1-x2| + |y1-y2|)로 측정한다.

가장 먼 집까지의 거리를 최소화했을 때 그 거리를 출력하시오.

제한

• 1 ≤ K ≤ 3