马拉松

题目描述

马拉松线路由 $N$ 个检查点（编号 $1 \sim N$）指定。检查点 $1$ 是起点，检查点 $N$ 是终点，贝茜要按顺序经过每个检查点。贝茜决定跳过其中一个检查点（不能跳过 $1$ 和 $N$），以缩短行程。请确定她需要行进的最短距离。两个检查站点 $(x_1, y_1)$ 与 $(x_2, y_2)$ 之间的距离为 $|x_1 - x_2| + |y_1 - y_2|$。

输入格式

第一行包含整数 $N$。接下来 $N$ 行，每行包含两个整数 $x, y$，表示一个检查点的横纵坐标。

输出格式

输出贝茜可以跳过一个检查点的情况下，需要行进的最短距离。

样例输入 #1

4
0 0
8 3
11 -1
10 0

样例输出 #1

14

数据范围

$3 \le N \le 10^5$，$-1000 \le x, y \le 1000$

知识点与难度

本题涉及的知识点从属于 GESP三级（枚举、前缀和），难度等级：⭐⭐⭐⭐⭐。

测试点分布