Problem Statement

There are $N$ points on a two-dimensional plane, and the $i$-th point is located at coordinates $\left( x_i, y_i \right)$. Here, all points are at distinct positions.
You will paint each of the $N$ points with one of the colors $1,2,3$. Here, the subtlety of a coloring is defined as follows.

• The maximum possible value of the Manhattan distance between the $2$ points, over pairs of $2$ points painted with the same color. However, if no pair of $2$ points painted with the same color exists, it is $0$.
• Here, for $2$ points $P_1(i_1,j_1),P_2(i_2,j_2)$, the Manhattan distance between $P_1$ and $P_2$ is $|i_1-i_2|+|j_1-j_2|$.

Find the subtlety when the points are colored so that the subtlety is minimized.

Input

$N$
$x_1\ \ y_1$
$x_2\ \ y_2$
$\vdots$
$x_N\ \ y_N$

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq x_i,y_i \leq 10^9$ $\left( 1 \leq i \leq N \right)$
• $\left( x_i,y_i \right) \neq \left( x_j,y_j \right)$ $\left( i \neq j \right)$
• All inputs are integers.

Output

Output the answer, followed by a newline.

Sample

5
2 2
1 3
3 2
4 1
3 3

2

3
1 1
2 2
3 3

0

10
57 71
29 39
46 32
85 19
34 57
79 13
60 72
55 46
79 12
13 18

47