题目描述

由于对奶牛们的健康状况不满，农夫约翰让它们参加了各种各样的体能活动。他的 prize 奶牛贝西参加了一个跑步班，最终她需要跑一场穿过农场附近城市市中心的马拉松！

马拉松路线由 N 个检查点（3 <= N <= 100,000）组成，需要按顺序访问，其中检查点 1 是起点，检查点 N 是终点。贝西本应一个接一个地访问所有这些检查点，但由于她是一头懒惰的奶牛，她决定最多跳过一个检查点来缩短总行程。不过，她不能跳过检查点 1 或 N，因为那样太明显了。

请帮助贝西计算如果她最多可以跳过一个检查点，她必须跑的最短距离。

请注意，由于赛道位于有街道网格的市中心，两个位于$(x1, y1)$和$(x2, y2)$的检查点之间的距离由$|x1 - x2| + |y1 - y2|$给出。这种通过 x 坐标差加上 y 坐标差来测量距离的方式有时被称为“曼哈顿”距离，因为它反映了在市中心网格中，你可以平行于 x 轴或 y 轴行进，但不能沿着直线“像乌鸦飞一样”行进。

输入格式

• 第 1 行：给出 N 的值。
• 接下来 N 行：每行包含两个空格分隔的整数 x 和 y，表示一个检查点（-1000 <= x <= 1000，-1000 <= y <= 1000）。检查点按必须访问的顺序给出。请注意，赛道可能会多次交叉，多个检查点可能出现在同一物理位置。当贝西跳过这样的检查点时，她只跳过该检查点的一个实例，而不是跳过所有出现在同一位置的检查点。

输出格式

• 第 1 行：输出贝西通过最多跳过一个检查点可以跑的最短距离。不要忘记在输出末尾加上换行符。

样例

样例输入

4
0 0
8 3
11 -1
10 0

样例输出

14

数据范围

3 <= N <= 100,000，检查点坐标范围为-1000 <= x, y <= 1000