뛰어넘을 수 있다면 뛰어 보라

펭귄 코만도들 사이에서 가장 인기 있는 놀이 중 하나가 「뛰어넘을 수 있다면 뛰어 보라」라는 게임이다.

규칙은 간단하다. 남극 먼 곳, 펭귄의 비밀 기지에 $n$개의 빙산이 한 줄로 서 있다. 각 빙산은 매우 높고 좁으며, 기준점으로부터의 거리 $x_i$와 높이 $y_i$로 주어진다. 참가자는 길이 $l$인 밧줄을 가지고 첫 번째 빙산의 꼭대기에 올라간다. 목표는 어떤 방법으로든 마지막 빙산에 도달하는 것이다. 밧줄을 이용해 펭귄은 두 빙산 꼭대기 사이의 거리가 밧줄 길이 이하이고 밧줄이 그 사이에 있는 어떤 빙산도 가로지르지 않으면, 한 빙산에서 다른 빙산으로 뛰어넘을 수 있다. (낮은 빙산에서 높은 빙산으로도, 높은 빙산에서 낮은 빙산으로도 뛰어넘을 수 있다는 점에 유의하라.) 게임의 승자는 대담하지만 계산적인 펭귄, 즉 가장 짧은 밧줄로 과제를 완수한 펭귄이다.

스키퍼는 자신과 팀원들에게 짧은 휴가를 주기로 했고, 당연히 그 남극 기지에서 휴가를 보내기로 했다. 마다가스카르에서 가는 길은 멀기 때문에, 팀에서 가장 영리한 코왈스키는 다가오는 대회를 잘 준비하려고 한다. 그는 마지막 빙산에 도달해 이기는 데 필요한 최소 밧줄 길이를 미리 알고 싶어 한다. 이런 것을 따지는 일은 펭귄에게 익숙하지 않은 일이라서, 그는 당신에게 도움을 청했다.

첫 줄에 정수 $n$ ($2 \le n \le 100000$)이 주어진다. 빙산의 개수다.

둘째 줄에는 $n$쌍의 정수 $x_i, y_i$ ($0 \le x_i < x_{i+1} \le 10^9$, $0 \le y_i \le 10^9$)가 주어진다. 빙산 꼭대기의 좌표다.

첫 번째 빙산에서 마지막 빙산까지 도달하는 데 필요한 밧줄의 최소 길이를 한 줄에 출력한다. 절대 오차 또는 상대 오차가 $10^{-6}$을 넘지 않으면 정답으로 인정한다.