2차원 평면상에 N 개의 점들이 주어졌을 때, 어느 한 점부터 시작하여 모든 점들을 단 한번 만 방문한 다음, 다시 그 점으로 돌아오는 가장 짧은 사이클(closed cycle)을 찾는 문제는 외판원 문제(TSP - Travelling Salesman Problem)로 잘 알려진 NP-hard 문제이다.

이 문제를 다항시간안에 해결하는 알고리즘은 아직 존재하지 않는다. 그러나 이 문제에 다음과 같은 제약조건을 넣어 단순화하면 다항시간안에 해결할 수 있다.

가장 왼쪽 점부터 시작하여 x-좌표가 증가하게 방문하여 가장 오른쪽 점에 방문한 다음 다시 x-좌표가 감소하게 방문하는 가장 짧은 사이클을 찾는다. 물론 이 때도 모든 N 개의 점을 방문해야한다.

그림 1	그림 2

<그림 1>은 일반적인 TSP cycle이나 Bitonic cycle은 아니다. 그러나 <그림 2>는 Bitonic cycle이다.

N 개의 점이 주어졌을 때, 이의 Bitonic cycle의 최적해를 구하는 프로그램을 작성하자.

입력

• 첫 줄에 점들의 개수 N 이 주어진다. (1 ≤ N ≤ 5,000)
• 그리고 다음 N 개의 줄에 점들의 좌표 (xi,yi) 가 주어진다. (단, xi 는 서로 다르고, xi,yi는 |xi| , |yi| ≤ 10,000 인 정수)

출력

입출력 예

입력

7
13 8
3 2
12 3
2 9
15 4
10 7
4 6

출력

36.61

출처: KOI 전국본선대비 모의고사(전명우) 2012년 7월 10일