Exposition

Time limit1sMemory limit128 MB

Summary

Split N points in the plane into two nonempty groups minimizing the largest Manhattan distance within any group.

Level: Hard8 of 10
Topics: Binary search, Geometry, Sorting
Solved: No attempts yet

Problem

A city is going to hold a large exposition. This exposition has two themes, and at each of the $N$ exhibition facilities in the city, exactly one of the two themes is chosen and an exhibition matching that theme is held.

The position of each facility is given by planar coordinates $(x, y)$ . Moving from a facility at $(x, y)$ to a facility at $(x', y')$ takes $|x - x'| + |y - y'|$ units of time (for an integer $a$ , $|a|$ denotes the absolute value of $a$ ). To create a sense of unity within each theme, and to avoid inconveniencing visitors interested in only one theme, we want to assign themes so that the travel time between any two facilities sharing the same theme is as small as possible. Any assignment is allowed except assigning the same theme to all facilities (that is, each of the two themes must be used by at least one facility).

Let $M$ be the maximum travel time between two facilities that share the same theme. Given the positions of the $N$ facilities, find the minimum possible value of $M$ .

Input

The first line contains the number of facilities $N$ ( $3 \le N \le 10^5$ ). Each of the next $N$ lines, the $(i+1)$ -th line ( $1 \le i \le N$ ), contains two integers $x_i$ and $y_i$ ( $|x_i| \le 10^5$ , $|y_i| \le 10^5$ ) separated by a space, meaning the $i$ -th facility is at $(x_i, y_i)$ . No two facilities share the same coordinates.

Output

Print, on a single line, the minimum possible value of the maximum travel time $M$ between two facilities that share the same theme.

Explanation

For example, assigning one theme to the facilities at $(0, 0)$ , $(1, 0)$ , $(0, 1)$ and the other theme to the facilities at $(-1, -2)$ , $(-1, 1)$ makes every travel time between two same-theme facilities at most $3$ . It is impossible to make all such travel times at most $2$ , so the answer is $3$ .

Examples3

Example 1
Input
```
5
0 0
1 0
-1 -2
0 1
-1 1
```
Expected output
```
3
```
Example 2
Input
```
3
0 0
1 1
2 0
```
Expected output
```
2
```

Example 3

Input

4
-100000 -100000
100000 100000
-100000 100000
100000 -100000

Expected output