5716 - 城市路径

地图上有n个城市,一只奶牛要从1号城市开始依次经过这些城市,最终到达n号城市。但是这只奶牛觉得这样太无聊了,所以它决定跳过其中的一个城市(但是不能跳过1号和n号城市),使得它从1号城市开始,到达n号城市所经过的总距离最小。假设每一个城市i都有一个坐标(xi,yi),从(x1,y1)的城市到(x2,y2)的城市之间的距离为|x1x2-|+|y1-y2|。

输入

第1行1个正整数n,表示城市个数。

接下来的n行,每行2个数xi和yi,表示城市i的坐标。

输出

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

样例

输入

4
0 0
8 3
11 -1
10 0

输出

14

提示

【样例说明】

跳过2号城市。

【数据规模】

对于40%的数据满足:n≤1000。

对于100%的数据满足:3≤n≤100000,-1000≤xi,yi≤1000。

 

来源

课课通

时间限制 1 秒
内存限制 256 MB
讨论 统计
上一题 下一题