题目描述

桂林的景点很多，为了让更多的游客可以顺利游玩。在不影响游览品质的前提下，旅游公司决定通过改变路线的方法分流游客。

方案是：每个旅行团都跳过其中的一个景点（但是不能跳过 1 号和 n 号景点），使得它从 1号景点开始，到达 n 号景点所经过的总距离最小。

假设每一个景点 $i$ 都有一个坐标 $(x_i,y_i)$，从 $(x_1,y_1)$ 的景点1到 $(x_2,y_2)$ 的景点2之间的距离为 $|x_1-x_2|+|y_1-y_2|$。

输入格式

第1行1个正整数 $n$，表示景点个数。接下来的 $n$ 行，每行2个数 $x_i$ 和 $y_i$，表示景点 $i$ 的坐标。

输出格式

一行一个数，使得它从1号景点开始，跳过某一个景点，到达n号景点所经过的最小总距离。

样例

输入

4
0 0
8 3
11 -1
10 0

输出

14

数据范围与提示

$n \leq 10^5$