题目描述

奶牛本来需要依次经过 $1,2,\ldots,n$ 号城市，现在允许跳过恰好一个城市，但不能跳过首尾。城市坐标为 $(x_i,y_i)$，两城市之间的距离为横坐标差的绝对值加纵坐标差的绝对值。求最小总路程。

输入格式

第一行城市数 $n$。接下来 $n$ 行，每行两个整数 $x_i,y_i$。

输出格式

输出跳过一个内部城市后的最短路程。

样例

4
0 0
8 3
11 -1
10 0

14

数据范围

对于 $40\%$ 的数据，$n\le1000$；对于 $100\%$ 的数据，$3\le n\le100000$，$-1000\le x_i,y_i\le1000$。