Given $N$ distinct points on a 2D plane, you would like to place three identical, axis-aligned squares on the plane such that every point is either inside or on the border on one of the squares.

Let $L$ be the side length of the squares. What is the minimum possible value of $L$ such that all the points can be covered?

Input Specification

The standard input will contain 10 datasets. Each dataset begins with an integer $N$ $(4\le N\le 100000)$. The next $N$ lines each contain two integers $X$, $Y$ $(-{10}^9\le X,Y\le {10}^9)$, the points in the plane.

For the first 4 cases, $N\le 30$.

Output Specification

For each dataset, output the value of $L$.

Sample Input (Two Datasets Shown)

4
1 1
2 2
3 3
4 4
5
1 1
2 1
-2 -1
4 4
-4 -2

Sample Output

1
2

Educational Computing Organization of Ontario - statements, test data and other materials can be found at ecoocs.org