题目描述

农夫约翰在他的谷仓里安装了一台别致的新挤奶机，但是它耗电太多，偶尔会导致停电！这种情况经常发生，以至于贝茜已经记住了一张谷仓的地图，这让她在黑暗中更容易找到谷仓的出口。她很好奇断电对她快速离开谷仓的能力有什么影响。例如，她想知道她需要走多远才能在黑暗中找到出口。

谷仓由一个简单的(非自交)多边形描述，其整数顶点 $(x_1,y_1)\ldots(x_n,y_n)$ 按顺时针顺序列出。其边缘在水平(平行于 $x$ 轴)和垂直(平行于 $y$ 轴)之间交替；第一条边可以是任何类型。出口位于 $(x_1,y_1)$ 。贝西从位于某个顶点 $(x_i,y_i)$ 的谷仓内开始，花费 $i \gt 1$ 。她只能绕着谷仓的周边走，或者顺时针，或者逆时针，当她到达顶点时可能会改变方向。她的目标是以最短的距离到达出口。当然，在灯亮着的情况下，这相对容易做到，因为她将从当前位置顺时针或逆时针行进到出口——无论哪个方向更短。

有一天，灯灭了，导致贝茜惊慌失措，忘记了自己正站在哪个顶点。幸运的是，她仍然记得谷仓的确切地图，所以她可能通过走动和使用她的触觉来找出她的位置。每当她站在一个顶点(包括在她初始的顶点)，她都能感觉到是左转还是右转，她能分辨出那个顶点是不是出口。当她沿着谷仓的边缘行走时，她可以在沿着整个边缘行走后确定边缘的精确长度。一般来说，贝西会有策略地在她的起始顶点周围摸索，直到她知道足够的信息来确定她在哪里，在这一点上，她可以很容易地找出如何通过行进最少的剩余距离到达出口。

请帮助贝茜确定在最糟糕的情况下(在她起始顶点的所有可能性上),她在黑暗中与在亮着灯的谷仓中行进时可能增加的最小距离，假设她在每种情况下都按照最佳策略移动。无照明情况下的“最佳”策略是最小化这个额外的最坏情况量。

输入格式

输入的第一行包含 $N$ ($4 \leq N \leq 200$)。接下来的$N$行中的每一行都包含两个整数，以顺时针顺序描述谷仓周围的点 $(x_i,y_i)$ 的情况。这些整数的范围是 $-100,000$ 到 $100,000$ 。

输出格式

请输出贝茜在黑暗中的最佳距离比她在明亮的谷仓中的最佳距离长的最小可能最坏情况量，其中最坏情况涵盖贝茜可以开始的所有可能顶点。

样例 #1

样例输入 #1

4
0 0
0 10
1 10
1 0

样例输出 #1

2

提示

在这个例子中，贝茜可以感觉到她最初站在一个向内的弯曲处，然而由于在这个例子中所有的拐角都是向内的弯曲处，这告诉她很少的信息。

一个最佳策略是顺时针方向行进。如果她从顶点 $3$ 或 $4$ 开始，这是最佳的，如果她从顶点 $2$ 开始，只增加 $2$ 个单位的距离。