A person has planted $N$ small saplings on a mountain. Winter has arrived, and the temperature has dropped rapidly. The saplings are too fragile to withstand the cold, so the owner wants to cover them with plastic sheets. After much thought, he decides to use $3$ square plastic sheets of size $L \times L$ to cover all the saplings. We can represent the mountain using a Cartesian coordinate system, where the coordinates of the $i$-th sapling are $(X_i, Y_i)$. The sides of the $3$ squares must be parallel to the coordinate axes. A point is considered covered if it lies on the boundary of a square. Naturally, we want the area of the plastic sheets to be as small as possible, which means we need to find the minimum value of $L$.

Input

The first line contains a positive integer $N$, representing the number of trees.

The next $N$ lines each contain two integers $X_i, Y_i$, representing the coordinates of the $i$-th tree. It is guaranteed that no two trees have the same coordinates.

Output

Output a single line containing the minimum value of $L$.

Constraints

• $100\%$ of the data: $-1,000,000,000 \le X_i, Y_i \le 1,000,000,000$
• $30\%$ of the data: $N \le 100$
• $50\%$ of the data: $N \le 2000$
• $100\%$ of the data: $N \le 20000$

Examples

Input 1

4
0 1
0 -1
1 0
-1 0

Output 1

1