描述

周幽王命令大臣代替他去巡视\(n\)个城市，回来重重有赏。大臣现在身处于第\(1\)个城市，要经过所有城市到达第\(n\)个城市。但周幽王不想做的事情大臣也不想做，于是他打算跳过一个城市，当然，不能跳过第\(1\)个和第\(n\)个城市。每一个城市有一个坐标，从城市\((x1,y1)\)到城市\((x2,y2)\)的距离为 \(|x1 - x2| + |y1 - y2|\)。而且他也想走过最少的距离，请求出从第\(1\)个城市到第\(n\)个城市的最短距离。

格式

输入格式

第一行一个数\(n\)，表示城市个数
接下一行\(n\) 行每行两个数\(x,y\)，表示每个城市的坐标

输出格式

一行一个数\(ans\), 使得大臣从\(1\) 号城市开始，跳过某一个城市，到达\(n\)号城市所经过的总距离最小。

样例1

输入样例1

4
0 0
8 3
11 -1
10 0

输出样例1

14

限制

对于\(100\)% 的数据，\(3<=n<=105，-103<=x<=103，-103<=y<=10^3\)。

来源

地址：\(vijos\)，芜湖\(OI\)团队
作者：黑暗路西法\(08\)
模拟赛\(T2\)