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는 당황해 현재 꼭짓점을 잊습니다. 정확한 지도는 기억하므로 걷고 만져 위치를 알아낼 수 있습니다. 각 꼭짓점 (시작점 포함)에서 정확한 내각을 느끼고 출구인지 알 수 있습니다. 변 하나를 끝까지 걷고 나면 그 정확한 길이를 알 수 있습니다. 충분한 각과 변을 느껴 현재 꼭짓점을 추론할 때까지 시계 방향으로 걷는 전략을 씁니다. 그 뒤 시계 방향을 계속 가거나 반시계 방향으로 바꿔 남은 최단 거리로 출구에 갑니다.

모든 가능한 시작 꼭짓점에 대한 최악의 경우, 어둠 속에서 불이 켜진 경우보다 걷는 거리가 얼마나 증가하는지 그 최댓값을 구하세요.

입력

첫 줄에는 $N$ ($4 \leq N \leq 200$)이 주어집니다. 다음 $N$줄마다 두 정수가 주어져 꼭짓점 $(x_i, y_i)$을 시계 방향으로 나타냅니다. 각 정수는 범위 $-100,000 \ldots 100,000$에 있습니다.

출력

설명된 전략을 쓸 때 최악의 시작 위치에서의 최대 거리 증가량을 출력하세요.

예제

입력 1

4
0 0
0 10
1 10
1 0

출력 1

2

참고

예제에서 Bessie는 시작 각이 90도인 것은 알지만 꼭짓점 2, 3, 4 중 어느 곳인지 모릅니다. 시계 방향으로 변 하나를 걸으면 출구에 도달하거나 그 변의 길이로 위치를 유일하게 알게 됩니다. 거리는 다음과 같습니다.

꼭짓점 2에서 시작: 어둠 속에서 12단위 (꼭짓점 3까지 1단위, 그 뒤 출구까지 11단위)를 걷지만 불이 켜지면 10단위만 필요합니다. 추가 거리는 2입니다.

꼭짓점 3에서 시작: 두 경우 모두 11단위입니다.

꼭짓점 4에서 시작: 두 경우 모두 1단위입니다.

따라서 최악의 차이는 $12 - 10 = 2$입니다. 이 전략은 어디에서 시작해도 불이 켜진 경우보다 어둠 속에서 최대 2단위만 더 걷게 됨을 보장합니다.

문제 출제: Brian Dean