{"raw_statement":[{"iden":"statement","content":"После успешного побега из здания подземной тюрьмы Галактической федерации соратники Сопротивления захватили бронированный автомобиль и теперь они должны добраться из точки P = (0, 0) в точку Q = (0, Yq). \n\nЗадача усложняется тем, что вокруг тюрьмы возведено множество стен, и чтобы покинуть тюрьму необходимо проехать последовательно через N ворот, которые представляет собой параллельные оси OX отрезки. \n\nВам необходимо посчитать длину кратчайшего пути из точки P в точку Q при условии, что путь должен проходить последовательно сквозь каждые ворота.\n\nВ первой строке задано число ворот N (1 ≤ N ≤ 105).\n\nВо второй строке задана Y-координата конечной точки Yq (2 ≤ Yq ≤ 109).\n\nВ следующих N строках заданы координаты ворот в виде троек чисел Yi, Xil, Xir (0 < Yi < Yq, Yi < Yi + 1,  - 109 ≤ Xil < Xir ≤ 109).\n\nВсе числа во входных данных целые.\n\nВыведите длину кратчайшего пути. Ответ считается правильным, если абсолютная или относительная погрешность не превосходит 10 - 6.\n\nКратчайший путь для теста из примера показан на рисунке:\n\n"},{"iden":"входные данные","content":"В первой строке задано число ворот N (1 ≤ N ≤ 105).Во второй строке задана Y-координата конечной точки Yq (2 ≤ Yq ≤ 109).В следующих N строках заданы координаты ворот в виде троек чисел Yi, Xil, Xir (0 < Yi < Yq, Yi < Yi + 1,  - 109 ≤ Xil < Xir ≤ 109).Все числа во входных данных целые."},{"iden":"выходные данные","content":"Выведите длину кратчайшего пути. Ответ считается правильным, если абсолютная или относительная погрешность не превосходит 10 - 6."},{"iden":"пример","content":"Входные данные351 -1 13 1 24 -2 -1Выходные данные6.812559200041"},{"iden":"примечание","content":"Кратчайший путь для теста из примера показан на рисунке:  "}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of gates.  \nLet $ Y_q \\in \\mathbb{R} $ be the $ y $-coordinate of the destination point $ Q = (0, Y_q) $.  \nLet $ P = (0, 0) $ be the starting point.  \nFor 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} $.\n\n**Constraints**  \n1. $ 1 \\leq N \\leq 10^5 $  \n2. $ 2 \\leq Y_q \\leq 10^9 $  \n3. For each $ i \\in \\{1, \\dots, N\\} $:  \n   - $ -10^9 \\leq X_{i,l} < X_{i,r} \\leq 10^9 $  \n   - $ 0 < Y_i < Y_q $  \n   - $ Y_i < Y_{i+1} $ (gates are ordered by increasing $ y $-coordinate)\n\n**Objective**  \nFind 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).\n\nThe total path length is:  \n$$\nL = \\sum_{i=0}^{N} \\sqrt{(x_{i+1} - x_i)^2 + (Y_{i+1} - Y_i)^2}\n$$  \nwhere $ 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\\} $.\n\nMinimize $ L $ over all valid choices of $ x_1, \\dots, x_N $.","simple_statement":"You start at (0, 0) and need to reach (0, Yq).  \nYou must pass through N gates in order.  \nEach gate i is a horizontal segment from (Xil, Yi) to (Xir, Yi), with 0 < Yi < Yq and Yi increasing.  \nFind the shortest path that goes through each gate in order.","has_page_source":false}