Farmer John は牛舎に豪華な新しい搾乳機を設置しましたが、消費電力が大きく、時々停電を起こします！あまりに頻繁なので Bessie は牛舎の地図を覚え、暗闇でも出口を見つけやすくしました。しかし停電が素早く出ることにどう影響するのか、例えば暗闇ではどれだけ余分に歩く必要があるのか気になっています。

牛舎は単純（自己交差しない）多角形で、整数座標の頂点 $(x_1, y_1) \ldots (x_n, y_n)$ が時計回りに並びます。辺は水平（$x$ 軸に平行）と垂直（$y$ 軸に平行）が交互で、最初の辺はどちらでも構いません。出口は $(x_1, y_1)$ です。Bessie は牛舎内の頂点 $(x_i, y_i)$、$i > 1$ にいます。周囲を時計回りか反時計回りにしか歩けず、最短距離で出口に着くことを目指します。明るければ、現在地から出口まで短い方の向きを選ぶだけなので簡単です。

ある日停電して、Bessie は慌てて自分がどの頂点にいるか忘れました。しかし正確な地図は覚えているので、歩いて触ることで位置を推測できます。頂点に立つと（初期頂点も含め）正確な内角を触って知ることができ、出口かどうかも分かります。辺の全長を歩き終えた後には、その正確な長さを知れます。Bessie は、十分な角度と辺を感じて現在の頂点を特定できるまで時計回りに歩く方針にします。特定後は、時計回りを続けるか反時計回りに切り替えて、残りの最短距離で出口へ行けます。

初期頂点の全候補にわたる最悪の場合に、暗い牛舎での歩行距離が明るい場合よりどれだけ増えるか、その最大値を求めてください。

入力

最初の行は $N$ ($4 \leq N \leq 200$) です。続く $N$ 行には 2 整数ずつあり、頂点 $(x_i, y_i)$ を時計回りに示します。各整数は範囲 $-100,000 \ldots 100,000$ にあります。

出力

問題文の方針を使うとき、最悪の初期位置での歩行距離の最大増加量を出力してください。

入出力例

入力 1

4
0 0
0 10
1 10
1 0

出力 1

2

注記

例では初期位置の角が 90 度と分かっても、頂点 2、3、4 のどれかは分かりません。時計回りに一辺を歩くと、出口に着くか辺長から位置を一意に特定できます。距離は次の通りです。

頂点 2 から：暗いと 12 単位（頂点 3 まで 1、その後出口まで 11）、明るいと 10 単位なので、余分な距離は 2 です。

頂点 3 から：どちらも 11 単位です。

頂点 4 から：どちらも 1 単位です。

したがって最悪の差は $12 - 10 = 2$ です。この方針では、どこから始めても暗闇で明るい場合より余分に歩く距離を最大 2 単位に抑えられます。

問題作成：Brian Dean