【问题描述】

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

【程序名】marathon

【输入格式】

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

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

【输出格式】

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

【输入样例】

4
0 0
8 3
11 -1
10 0

【输出样例】

14

【样例说明】

跳过2号城市。

【数据规模】

对于40％的数据满足：n≤1000。

对于100％的数据满足：3≤n≤100000，-1000≤xi，yi≤1000。