33835번 - 도로 공사 스페셜 저지

문제

$xy$평면 위에 1ドル$번부터 $N$번까지 총 $N$개의 마을이 있다. $i$번 마을의 좌표는 $(x_i, y_i)$이고, 각 마을의 좌표는 서로 다르다.

두 마을 사이에는 둘만을 연결하는 도로를 지을 수 있고, 이 도로의 길이는 두 마을 사이의 유클리드 거리^[1] 와 같다. 처음에 $j$번 마을과 $j+1$번 마을을 연결하는 도로가 하나씩 존재한다. $(1 \le j \le N-1)$

여러분은 초기 건설 자원이 0ドル$인 상태에서, 다음 2가지 공사를 각각 원하는 만큼 수행할 수 있다.

• 현재 설치된 도로 중 하나를 철거한다. 이때 건설 자원이 철거한 도로의 길이만큼 늘어난다.
• 원하는 두 마을을 연결하는 도로를 건설한다. 이때 건설 자원이 도로의 길이만큼 소모되며, 소모할 건설 자원이 부족하면 건설할 수 없다.

1ドル$번 마을에서 $N$번 마을에 도착하기까지 도로만을 이용하여 이동할 때, 지나는 도로의 총 길이의 최솟값을 구하여라.

입력

첫 번째 줄에 마을의 개수 $N$이 주어진다. $(2 \le N \le 100,000円)$

두 번째 줄부터 $N$개의 줄에 걸쳐 마을의 좌표가 주어진다. 그중 $i$번째 줄에는 $i$번 마을의 좌표를 나타내는 정수 $x_i,ドル $y_i$가 공백으로 구분되어 주어진다. 각 마을의 좌표는 서로 다르다. $(-10^9 \le x_i, y_i \le 10^9)$

출력

첫 번째 줄에 1ドル$번 마을에서 $N$번 마을에 도착하기까지 지나는 도로의 총 길이의 최솟값을 출력한다. 절대/상대 오차는 10ドル^{-4}$까지 허용한다.

제한

노트

[1] $xy$평면 위에서 $(a, b)$와 $(c, d)$의 유클리드 거리는 $\sqrt{(a-c)^2 + (b-d)^2}$이다.