두 바퀴 위의 담합

메트로 시티에서 자전거 택배 회사 두 곳이 여러 해 동안 경쟁해 왔다. 두 회사는 서로의 고객을 번갈아 빼앗아 왔다. 최근 두 회사는 새 고객을 끌어들이는 편이 낫다는 것을 깨달았다. 문제는 고객들이 도시 곳곳에 흩어져 있어서 일부 고객의 배송 시간이 받아들이기 어려울 만큼 길다는 점이다. 그 결과 고객 불만이 커졌고 평판도 나빠졌다.

두 회사는 새 고객을 모으기 위해 "최대 M분 안에 배송을 보장합니다"라는 광고를 각각 내고 싶어 한다. 그러려면 현재 고객을 두 회사에 나누어 배정해야 한다. 메트로 시티의 도로는 격자 모양이고, 건물은 격자의 정수 좌표에 있다. 택배 기사는 도로를 따라 이동해야 하며 건물을 가로질러 갈 수 없다. x 방향이나 y 방향으로 단위 거리를 이동하는 데 1분이 걸린다.

기사가 한 회사의 고객에서 같은 회사의 다른 고객으로 이동할 때 걸리는 배송 시간의 최댓값이, 두 회사 모두에 대해 가능한 한 작아지도록 현재 고객을 나누어라.

• 배송은 기사가 고객의 (x, y) 주소에 도착하는 순간 완료된다. 고객의 건물 안을 돌아다니는 시간은 세지 않는다.
• 한 고객에서 다른 고객으로 이동하는 기사는 어느 회사의 고객이든 지나칠 수 있다. 지나치는 것만으로는 추가 지연이 생기지 않는다.
• 한 회사에 고객이 한 명만 남으면, 그 회사는 건물 안에서 메시지를 전달할 사람을 둔다. 이때 배송 시간은 0으로 본다.

첫 줄에 나눌 고객의 수 N이 주어진다. $2 < N \leq 1000$이다.

이어지는 N줄에는 고객 한 명의 위치를 나타내는 정수 x와 y가 주어진다. $0 \leq x, y \leq 1000$이다.

두 회사가 각각 구한 가장 긴 배송 시간 중 더 큰 값을 한 줄에 출력한다. 즉, 각 회사별 최장 배송 시간 두 값의 최댓값이다.