Migrated from Lutece 2980 滑冰

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

在企鹅国，企鹅们是通过滑冰出行的，企鹅国有 $n$ 个营地，分别编号为 $1$ 至 $n$，$i$号营地位于点 $(x_i,y_i)$。 每次滑冰需要选择一个营地作为起点，一个营地作为终点，然后从营地 $A$ 滑到营地 $B$ 需要的时间是 $\min(|x_A-x_B|, |y_A-y_B|)$。 现在企鹅豆豆在 $1$ 号营地，他需要赶到 $N$ 号营地参加活动，他想知道他最少需要花费多少时间？ 可能存在营地重合的情况。

Input

第一行一个整数 $n(1\le n\le 2\times 10^5)$，代表营地个数； 接下来 $n$ 行，每行 $2$ 个数字 $x_i, y_i(0\le x_i,y_i\le 10^9)$，表示一个营地的坐标；

Output

Samples

5
2 2
1 1
4 5
7 1
6 7

2

Resources

2023 UESTC ICPC Training for Graph