После успешного побега из здания подземной тюрьмы Галактической федерации соратники Сопротивления захватили бронированный автомобиль и теперь они должны добраться из точки P = (0, 0) в точку Q = (0, Yq).
Задача усложняется тем, что вокруг тюрьмы возведено множество стен, и чтобы покинуть тюрьму необходимо проехать последовательно через N ворот, которые представляет собой параллельные оси OX отрезки.
Вам необходимо посчитать длину кратчайшего пути из точки P в точку Q при условии, что путь должен проходить последовательно сквозь каждые ворота.
В первой строке задано число ворот N (1 ≤ N ≤ 105).
Во второй строке задана Y-координата конечной точки Yq (2 ≤ Yq ≤ 109).
В следующих N строках заданы координаты ворот в виде троек чисел Yi, Xil, Xir (0 < Yi < Yq, Yi < Yi + 1, - 109 ≤ Xil < Xir ≤ 109).
Все числа во входных данных целые.
Выведите длину кратчайшего пути. Ответ считается правильным, если абсолютная или относительная погрешность не превосходит 10 - 6.
Кратчайший путь для теста из примера показан на рисунке:
## Входные Данные
В первой строке задано число ворот N (1 ≤ N ≤ 105).Во второй строке задана Y-координата конечной точки Yq (2 ≤ Yq ≤ 109).В следующих N строках заданы координаты ворот в виде троек чисел Yi, Xil, Xir (0 < Yi < Yq, Yi < Yi + 1, - 109 ≤ Xil < Xir ≤ 109).Все числа во входных данных целые.
## Выходные Данные
Выведите длину кратчайшего пути. Ответ считается правильным, если абсолютная или относительная погрешность не превосходит 10 - 6.
## Пример
Входные данные351 -1 13 1 24 -2 -1Выходные данные6.812559200041
## Примечание
Кратчайший путь для теста из примера показан на рисунке:
[samples]
**Definitions**
Let $ N \in \mathbb{Z} $ be the number of gates.
Let $ Y_q \in \mathbb{R} $ be the $ y $-coordinate of the destination point $ Q = (0, Y_q) $.
Let $ P = (0, 0) $ be the starting point.
For each $ i \in \{1, \dots, N\} $, let the $ i $-th gate be a horizontal segment $ G_i = [X_{i,l}, X_{i,r}] \times \{Y_i\} $, where $ 0 < Y_i < Y_q $ and $ Y_i < Y_{i+1} $.
**Constraints**
1. $ 1 \leq N \leq 10^5 $
2. $ 2 \leq Y_q \leq 10^9 $
3. For each $ i \in \{1, \dots, N\} $:
- $ -10^9 \leq X_{i,l} < X_{i,r} \leq 10^9 $
- $ 0 < Y_i < Y_q $
- $ Y_i < Y_{i+1} $ (gates are ordered by increasing $ y $-coordinate)
**Objective**
Find the minimum length of a path from $ P = (0, 0) $ to $ Q = (0, Y_q) $ that intersects each gate $ G_i $ in order (i.e., the path must pass through some point $ (x_i, Y_i) \in G_i $ for each $ i $, and the sequence of points $ (0,0), (x_1,Y_1), (x_2,Y_2), \dots, (x_N,Y_N), (0,Y_q) $ forms a polygonal chain).
The total path length is:
$$
L = \sum_{i=0}^{N} \sqrt{(x_{i+1} - x_i)^2 + (Y_{i+1} - Y_i)^2}
$$
where $ x_0 = 0 $, $ Y_0 = 0 $, $ x_{N+1} = 0 $, $ Y_{N+1} = Y_q $, and $ x_i \in [X_{i,l}, X_{i,r}] $ for $ i \in \{1, \dots, N\} $.
Minimize $ L $ over all valid choices of $ x_1, \dots, x_N $.