Smeshariki Gathering Time

Time limit2sMemory limit1024 MB

Summary

Find the minimum seconds for n people on an integer grid to meet at one lattice point, moving up, down, left, right, or staying put each second.

Level: Medium6 of 10
Topics: Math, Greedy
Solved: No attempts yet

Statement

A new Smeshariki season has started, and everyone is going on a hike. First, they must meet at one point, and only then set off to explore the world. Losyash, who coordinates the group, knows the coordinates of every participant. Find the minimum number of seconds the Smeshariki need to gather in one place.

Initially, every Smeshariki stands on a point of the integer grid. If a Smeshariki is at $(x, y)$ , then in one second it can move to $(x, y + 1)$ , $(x + 1, y)$ , $(x - 1, y)$ , or $(x, y - 1)$ , or stay at $(x, y)$ .

Input

The first line contains one integer $n$ , the number of Smeshariki ( $1 \le n \le 200\,000$ ). Each of the next $n$ lines contains the starting position of one Smeshariki, given by two integers $x_i$ and $y_i$ ( $-10^{18} \le x_i, y_i \le 10^{18}$ ).

Output

Print a single number, the minimum number of seconds the Smeshariki need to gather in one point.

Examples3

Example 1
Input
```
1
1 1
```
Expected output
```
0
```
Example 2
Input
```
2
1 3
4 4
```
Expected output
```
2
```
Example 3
Input
```
3
0 0
3 3
0 3
```
Expected output
```
3
```