시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 128 MB 42 8 6 23.077%

문제

용인 시는 버스 정류장이 N개 있는 버스 노선을 짜려고 한다. 각 버스 정류장은 거리의 모퉁이에 있다. 용인 시는 현대적으로 설계된 도시이기 때문에 지리 구조가 정사각형 격자 모양으로 짜여 있다. 우리는 이 버스 정류장들 가운데 두 곳을, 중심지로서 H1, H2라는 이름으로 선택하려고 한다. 중심지를 선택하고 나면, 두 중심지 사이에는 버스가 가는 길이 생기며, 중심지를 제외한 나머지 N-2개의 버스 정류장들은 H1 아니면 H2 중 한 곳(두 중심지 모두와 연결되는 것은 아님.)과 직통하게 될 것이다. 이렇게 버스 노선이 결정된다.

이 문제에서 임의의 두 지점 사이의 거리는, 두 곳을 수평 수직 방향으로만 통행하는 가장 가까운 거리이다. 다시 말해, 위치를 (x, y) 좌표로 표현했을 때, 두 지점 (x1, y1)과 (x2, y2)의 거리는 |x1-x2|+|y1-y2|로 정의된다는 뜻이다. 한편, 버스 정류장 A와 B가 같은 중심지 H1과 연결돼 있으면 두 정류장 사이의 거리는 A와 H1 사이의 거리와 H1과 B 사이의 거리의 합이 된다. 그리고 A와 B가 각각 다른 중심지인 H1, H2와 연결돼 있으면 두 정류장 사이의 거리는 A와 H1, H1과 H2, H2와 B 사이의 거리들의 합이 된다.

용인 시의 도시 계획부는, 모든 시민이 도시의 모든 구역에 최대한 빨리 도착할 수 있게 하길 원한다. 따라서 도시 계획자들은 버스 정거장들 중, 서로 가장 멀리 떨어져 있는 두 곳 사이의 거리를 최소화할 수 있게끔 중심지 두 곳을 고르려고 한다. 이 거리를 최소화하게 중심지를 고른 뒤, 서로 거리가 가장 먼 두 정류장 사이의 거리를 계산하는 프로그램을 작성하시오.

입력

첫째 줄에는 버스 정류장의 개수인 정수 N(2≤N≤500)이 있다. 그리고 다음 N 개의 줄에는 버스 정류장의 x, y좌표가 있다. (가로 먼저, 다음 세로) 각 좌표들은 5000과 같거나 작은 자연수이다. 정류장들은 모두 서로 다른 위치에 있으며, 겹치는 경우가 없다.

출력

거리가 가장 먼 두 정류장 사이의 거리의 최소값을 나타내는 자연수 하나를 한 줄에다 출력한다.

예제 입력

6
1 7
16 6
12 4
4 4
1 1
11 1

예제 출력

20

힌트