题目描述

Berland 的一条铁路在平面上是一条可能自交、但不会出现线段重合覆盖的折线。折线的每一条线段都平行于坐标轴，列出的顶点顺序就是列车沿铁路行驶时经过这些顶点的顺序。

现在需要确定列车的最大长度。列车在铁路上行驶时，占据铁路上的一段连续区间。为了安全，在任意时刻列车在平面上都不能发生自相交或自接触。唯一允许的例外是：列车的车头和车尾可以恰好位于同一个点。

忽略铁轨和列车的宽度，将其视为宽度为 $0$ 的曲线。求列车允许的最大长度。

输入格式

第一行包含一个整数 $N$，表示折线的顶点数。

接下来 $N$ 行，每行两个整数 $x_i,y_i$，表示第 $i$ 个顶点的坐标。

保证：

• $1\le N\le 4000$；
• $|x_i|,|y_i|\le 10000$；
• 相邻顶点形成的线段均平行于坐标轴；
• 折线不存在两条线段重合覆盖的情况。

输出格式

输出一个整数，表示列车允许的最大长度。

样例 1

样例输入

5
0 0
3 0
3 1
1 1
1 -1

样例输出

6

样例 2

样例输入

7
0 0
1 0
1 1
3 1
3 0
1 0
1 -1

样例输出

6