Three Squares

Time limit1sMemory limit256 MB

Summary

Given N integer points, find the smallest side length L so that three equal axis-parallel squares of side L can cover every point.

Level: Hard8 of 10
Topics: Binary search, Sorting, Greedy, Divide and conquer
Solved: No attempts yet

Problem

There are $N$ distinct points in the plane, and every point has integer coordinates. Place three axis-parallel squares of the same side length so that each of the $N$ points lies inside one of the squares or on its border. Find the smallest side length for which this is possible.

The squares can be placed anywhere in the plane, and they can overlap.

Input

The first line contains the number of points $N$ ( $1 \le N \le 100\,000$ ).

Each of the next $N$ lines contains the $x$ and $y$ coordinates of one point, separated by a space ( $0 \le x, y \le 10^9$ ). All points are distinct.

Output

Print, on one line, the smallest side length of three equal squares that cover all $N$ points. This value is always an integer.

Hint

In the first example, three squares of side length 2 with bottom left corners at $(0, 0)$ , $(8, 0)$ , and $(7, 1)$ cover all five points.

Examples3

Example 1
Input
```
5
0 0
10 0
0 1
2 2
9 3
```
Expected output
```
2
```
Example 2
Input
```
1
1000000000 1000000000
```
Expected output
```
0
```
Example 3
Input
```
7
0 7
4 7
9 7
13 7
20 7
26 7
31 7
```
Expected output
```
9
```