In Bob's country, there are ~N~ cities, numbered from ~1~ to ~N~. The ~i~-th city is located at coordinates ~(x_i, y_i)~ on a 2D plane. There are initially ~N-1~ roads connecting the cities in sequence. For each ~i~ from ~1~ to ~N - 1~, there is a road between city ~i~ and city ~i+1~. The length of this road is defined by the Manhattan distance between the two cities, i.e. ~|x_i - x_{i+1}| + |y_i - y_{i+1}|~.

A path from city ~i~ to city ~j~ is a sequence of roads that allows people to travel from ~i~ to ~j~. The length of a path is the sum of the lengths of the roads in that path. The diameter of the country is defined as the longest shortest path between any two cities.

To reduce the diameter, Bob is allowed to build one additional road between any pair of distinct cities ~i~ and ~j~ (~1 \le i < j \le N~). The new road's length is also defined by the Manhattan distance between the two cities.

Bob wants to choose the best pair of cities to build this new road such that the resulting diameter of the country is minimized. Can you help him find the shortest diameter?

Input Specification

The first line contains an integer ~N~ (~3 \le N \le 2.5 \times 10^5~), the number of cities.

Each of the following ~N~ lines contains two integers ~x_i~, ~y_i~ (~-10^9 \le x_i, y_i \le 10^9~), the coordinates of the ~i~-th city.

Output Specification

Output one integer, the minimum diameter after adding one optimal road.

Constraints

Subtask	Points	Additional constraints
~1~	~4~	~N \le 40~
~2~	~6~	~N \le 100~.
~3~	~12~	~N \le 300~.
~4~	~25~	~N \le 2\,000~.
~5~	~23~	~N \le 50\,000~.
~6~	~30~	No additional constraints

Sample Input

4
1 2
3 3
4 1
2 3

Sample Output

6

Explanation for Sample

Bob can build the new road between city ~2~ and city ~4~. The new diameter will be the path from city ~1~ to city ~3~ with the length of ~6~.