Description

Someone planted $N$ saplings on a mountain. Winter has come, the temperature dropped sharply, and the saplings are too fragile. The owner wants to cover them with some plastic sheets. After careful consideration, he decides to use $3$ square plastic sheets of size $L \times L$ to cover the saplings. We set up a 2D Cartesian coordinate system on the mountain; the coordinates of the $i$-th sapling are $(X_i, Y_i)$. The $3$ squares of size $L \times L$ must be axis-aligned. A point lying on the boundary of a square is also considered covered. Of course, we want the plastic area to be as small as possible; that is, find the minimal $L$.

Input Format

The first line contains an integer $N$.
The next $N$ lines each contain two integers $X_i, Y_i$, giving the coordinates of the $i$-th tree. It is guaranteed that no two trees share the same coordinates.

Output Format

Output one line: the minimal value of $L$.

4
0 1
0 -1
1 0
-1 0

1

Hint

For $100\%$ of the testdata, $-1,000,000,000 \le X_i, Y_i \le 1,000,000,000$.

For $30\%$ of the testdata, $N \le 100$.

For $50\%$ of the testdata, $N \le 2000$.

For $100\%$ of the testdata, $N \le 20000$.

Translated by ChatGPT 5