Exposition

A city is going to hold a large exposition. This exposition has two themes, and at each of the $N$ exhibition facilities in the city, exactly one of the two themes is chosen and an exhibition matching that theme is held.

The position of each facility is given by planar coordinates $(x, y)$. Moving from a facility at $(x, y)$ to a facility at $(x', y')$ takes $|x - x'| + |y - y'|$ units of time (for an integer $a$, $|a|$ denotes the absolute value of $a$). To create a sense of unity within each theme, and to avoid inconveniencing visitors interested in only one theme, we want to assign themes so that the travel time between any two facilities sharing the same theme is as small as possible. Any assignment is allowed except assigning the same theme to all facilities (that is, each of the two themes must be used by at least one facility).

Let $M$ be the maximum travel time between two facilities that share the same theme. Given the positions of the $N$ facilities, find the minimum possible value of $M$.

The first line contains the number of facilities $N$ ($3 \le N \le 10^5$). Each of the next $N$ lines, the $(i+1)$-th line ($1 \le i \le N$), contains two integers $x_i$ and $y_i$ ($|x_i| \le 10^5$, $|y_i| \le 10^5$) separated by a space, meaning the $i$-th facility is at $(x_i, y_i)$. No two facilities share the same coordinates.

Print, on a single line, the minimum possible value of the maximum travel time $M$ between two facilities that share the same theme.

For example, assigning one theme to the facilities at $(0, 0)$, $(1, 0)$, $(0, 1)$ and the other theme to the facilities at $(-1, -2)$, $(-1, 1)$ makes every travel time between two same-theme facilities at most $3$. It is impossible to make all such travel times at most $2$, so the answer is $3$.