Problem Description

Xiao Lan is traveling in a certain country. The cities in this country are arranged on a hexagonal grid, as shown in the figure. Each hexagon in the figure represents a city.

:::align{center} :::

If two cities share a common edge, then Xiao Lan can move from one city to the other in one step.

For any two cities, if it takes at least $k$ steps to walk from one city to the other, then the distance between these two cities is defined as $k$. In other words, the distance here is the minimum number of steps between the two cities.

Each city can be represented by a unique coordinate $(x, y)$. Its meaning is: starting from the city with coordinate $(0, 0)$, first walk $x$ steps along the $X$ direction, then walk $y$ steps along the $Y$ direction, and you will reach that city.

Now you are given the coordinates of $n$ cities. You need to find, among these $n$ cities, the distance between the two cities that are farthest apart.

Input Format

The first line contains a positive integer $n$, indicating the number of cities given.

The next $n$ lines each contain two integers $x_i, y_i$, representing the coordinates of the $i$-th city.

Output Format

Output one line containing one integer, representing the distance between the two farthest cities among the given $n$ cities.

4
0 -1
-1 -1
2 2
4 2

5

Hint

Sample Explanation

These four cities are exactly the four cities marked in the figure.

Among them, the farthest pair of cities is $(-1, -1)$ and $(4, 2)$. Starting from $(-1, -1)$, you can first walk 3 steps in the upper-right direction to reach $(2, 2)$; then walk 2 steps along the positive direction of the $X$ axis to reach $(4, 2)$.

The shortest distance between these two cities is 5, so the answer is 5.

Constraints

For $50\%$ of the testdata, $n \le 3000$.

For all testdata, $2 \le n \le 3 \times 10^5$, $|x_i|, |y_i| \le 10^9$.

Translated by ChatGPT 5