박람회

어느 도시에서 대규모 박람회를 개최한다. 이번 박람회에는 두 가지 테마가 있으며, 도시에 있는 $N$개의 전시 시설 각각에서 두 테마 중 정확히 하나를 골라 그 테마에 맞는 전시를 진행한다.

각 시설의 위치는 평면 좌표 $(x, y)$로 나타난다. 위치 $(x, y)$의 시설에서 위치 $(x', y')$의 시설로 이동하는 데에는 $|x - x'| + |y - y'|$만큼의 시간이 걸린다(정수 $a$에 대해 $|a|$는 $a$의 절댓값을 뜻한다). 같은 테마 안에서의 통일감을 주고, 한쪽 테마에만 관심 있는 사람이 불편을 느끼지 않도록, 같은 테마로 전시하는 두 시설 사이의 이동 시간이 되도록 짧아지게 테마를 배정하려 한다. 단, 모든 시설에 같은 테마를 배정하는 경우만 아니라면 어떤 방식으로 배정해도 좋다(즉, 두 테마 각각에 적어도 하나의 시설이 배정되어야 한다).

같은 테마로 전시하는 두 시설 사이 이동 시간의 최댓값을 $M$이라 하자. $N$개 시설의 위치가 주어질 때, $M$의 최솟값을 구하여라.

첫째 줄에 시설의 개수 $N$ ($3 \le N \le 10^5$)이 주어진다. 이어지는 $i+1$번째 줄 ($1 \le i \le N$)에는 $i$번째 시설의 좌표를 나타내는 두 정수 $x_i$, $y_i$ ($|x_i| \le 10^5$, $|y_i| \le 10^5$)가 공백으로 구분되어 주어진다. 같은 좌표에 두 개 이상의 시설이 존재하는 경우는 없다.

같은 테마로 전시하는 두 시설 사이 이동 시간의 최댓값 $M$의 최솟값을 한 줄에 출력한다.

예를 들어 좌표 $(0, 0)$, $(1, 0)$, $(0, 1)$의 시설에 한 테마를, $(-1, -2)$, $(-1, 1)$의 시설에 다른 테마를 배정하면 같은 테마로 전시하는 두 시설 사이 이동 시간이 모두 $3$ 이하가 된다. 모든 이동 시간을 $2$ 이하로 만드는 것은 불가능하므로 답은 $3$이다.