Слалом#1257

Слалом

1 секунда

64 мегабайти

Дуже легка

Незважаючи на рідкісні снігопади в Мадриді, інтерес до зимових видів спорту в місті зростає, особливо до катання на лижах. Багато людей проводять декілька вихідних або навіть цілі тижні, вдосконалюючи свої навички в горах.

У цій задачі нас цікавить лише одна з багатьох дисциплін гірськолижного спорту — слалом. Трасу створюють, розставляючи серію воріт, які складаються з двох жердин. Лижник має проїхати між двома жердинами, що утворюють кожні ворота. Перемагає той спортсмен, який проходить трасу за найменший час і не пропускає жодних воріт.

Ви нещодавно почали вчитися кататися на лижах, але вже поставили собі за мету взяти участь у зимових Олімпійських іграх $2018$ року, для яких Мадрид, ймовірно, подасть заявку. У рамках теоретичної підготовки вам потрібно написати програму, яка за заданою стартовою точкою та серією воріт обчислює мінімально можливу довжину шляху, що починається у зазначеній точці, проходить через кожні ворота (у зазначеному порядку) й закінчується на останніх воротах, які є фінішною лінією. Ви можете вважати, що ворота горизонтальні й впорядковані від найвищих до найнижчих, тобто ви повинні проходити їх у відповідному порядку. Ви вважаєте себе вправним лижником, тому можете здійснювати будь-які повороти, якими складними б вони не були, і ваша єдина мета — мінімізувати загальну довжину шляху.

Вхідні дані

У першому рядку кожного випадку вказано кількість воріт $n$ ( $1 \leq n \leq 1000$ 1 \le n \le 1000). У наступному рядку містяться два дійсних числа — декартові координати $x$ та $y$ стартової позиції (у такому порядку). Далі йде $n$ рядків, у кожному з яких по три дійсних числа: $y x_{1} x_{2}$ y\ x_1\ x_2, що означає, що наступні ворота — це горизонтальний відрізок від $(x_{1}, y)$ (x_1, y) до $(x_{2}, y)$ (x_2, y). Гарантується, що $x_{1} < x_{2}$ x_1 < x_2. Значення $y$ строго спадають і завжди менші за $y$ стартової точки. Останні ворота є фінішною лінією. Всі координати належать проміжку від $- 500000$ до $500000$ включно. Значення $0$ для $n$ означає кінець вводу. Після кожного тесту іде порожній рядок.

Вихідні дані

Для кожного тесту виведіть рядок із мінімальною довжиною шляху, необхідною для досягнення фінішної лінії. Ваша відповідь має бути точною з абсолютною або відносною похибкою не більше $1 0^{- 7}$ 10^{-7}.

Приклади

Приклад 1