283_cable_car

Канатная дорога

Description

Одному альпинисту очень нравится посещать вершины Уральских гор. Известно, что Уральский хребет не славится высокими горами, однако, его протяжённость впечатляет. Поэтому посещение всех вершин занимает ужасно много времени. Чтобы ускорить этот процесс, альпинист решил построить канатную дорогу.

В качестве отправной точки альпинист выбрал центр своего города. Затем определил координаты всех вершин, относительно этого центра. Оказалось, что все они лежат на одной прямой. Для начала, альпинист решил последовательно соединить вершины канатной дорогой, начиная от центра города. Однако, некоторые горы на этом маршруте оказались слишком низкими и скучными. Поэтому альпинист также решил соединить каждую вершину со следующей, не меньшей по высоте, если такая существует.

План альпиниста очень понравился мэру города! Чтобы правильно составить смету, он попросил вас вычислить суммарную длину такой канатной дороги. Вы против коррупции, поэтому решили произвести расчеты максимально точно.

Input Format:

Первая строка входных данных содержит целое число $N$ ($1 \le N \le 2 \cdot 10^5$) — количество горных вершин, через которые пройдет канатная дорога. Каждая из следующих $N$ строк содержит два целых числа $x_i, y_i$ ($1 \le x_i, y_i \le 10^9$) — расстояние и высота каждой вершины относительно центра города. Все вершины имеют различные расстояния от центра города и заданы в порядке их возрастания.

Output Format:

В единственной строке выведите одно число — суммарную длину канатной дороги.

Ваш ответ будет засчитан, если относительная или абсолютная погрешность не будет превышать $10^{-9}$. Формально если $a$ — ваш ответ, а $b$ — ответ жюри, то он будет засчитан если $\frac{|a - b|}{max(b,1)} \le 10^{-9}$.

Example Test Cases

Example 1

Input:

6
3 2
5 1
7 4
9 3
11 7
12 1

Output:

31.710272946225