There are $N$ cities located at distinct positions on a plane. These cities are numbered with integers from $1$ to $N$. There is a road between city $i$ and city $i+1$, denoted as $R_i$ (for $i=1, \dots, N-1$). Thus, there are a total of $N-1$ roads. For each $i=1, \dots, N-1$, if the coordinates of city $i$ are $(x_i, y_i)$, the length of road $R_i$ is defined as $|x_i-x_{i+1}|+|y_i-y_{i+1}|$.

A path $P$ between city $i$ and city $j$ is the set of roads traversed when moving from $i$ to $j$. The length of path $P$ is the sum of the lengths of all roads in $P$. We are interested in the diameter of the set of cities. The diameter is defined as the maximum value of the shortest path length between all pairs of cities. In the given city structure, the diameter of the cities is equal to the length of the path between city $1$ and city $N$.

We plan to select a pair of cities and build a new road. Let this new road be denoted as $R_{\text{new}}$. If $R_{\text{new}}$ connects city $a$ and city $b$, its length is defined as $|x_a-x_b|+|y_a-y_b|$. The problem is to choose the new road $R_{\text{new}}$ such that the diameter of the set of cities is minimized.

Given the positions of $N$ cities, write a program to determine the new road $R_{\text{new}}$ that minimizes the diameter of the cities and output the minimum diameter.

For example, the figure below shows $4$ cities and the $3$ roads connecting them (solid lines). There are $3$ candidate roads that can be newly built (between city $1$ and $4$, $1$ and $3$, or $4$ and $2$). As shown in the figure, if a new road is built between city $4$ and city $2$ (dashed line), the diameter of the cities becomes $6$, which is the minimum value.

You must implement the following function for the judging system and submit your answer using this function:

• long long shortcut(int N, long long X[], long long Y[]); This function takes the number of cities $N$, and arrays X[0..N-1] and Y[0..N-1] representing the positions of each city as parameters. X[] and Y[] are vectors of length $N$, where X[i] and Y[i] represent the $x$-coordinate and $y$-coordinate of city $i+1$, respectively. The return value of the function is the minimum possible value of the city diameter after the new road is added.

Implementation Details

You must submit exactly one file named shortcut.cpp. This file must implement the following function:

• long long shortcut(int N, long long X[], long long Y[]);

The behavior of this function should be consistent with the description above. You may define and use other functions internally. The submitted code must not perform input/output operations, nor may it access other files.

Example Grader

The provided grader will read the input in the following format:

• Line 1: $N$ (number of cities, $3 \le N \le 250{,}000$)
• Lines 2 to $N+1$: The $i$-th line gives the coordinates $(x,y)$ of city $i-1$, where $-10^9 \le x,y \le 10^9$

The grader will output the minimum diameter of the cities after the new road is added.

Subtasks

• Subtask 1 (4 points): $N \le 40$
• Subtask 2 (6 points): $N \le 100$
• Subtask 3 (12 points): $N \le 300$
• Subtask 4 (25 points): $N \le 2{,}000$
• Subtask 5 (40 points): $N \le 50{,}000$
• Subtask 6 (13 points): No additional constraints

Examples

Input 1

4
1 2
2 2
2 1
1 1

Output 1

2

Input 2

4
1 2
3 3
4 1
2 3

Output 2

6