Slalom
Madriddə qar yağışının az olmasına baxmayaraq, şəhərdə qış idman növlərinə, xüsusilə xizəksürməyə maraq artır. Bir çox insan bacarıqlarını dağlarda təkmilləşdirmək üçün bir neçə həftəsonu və ya hətta tam həftələr keçirir.
Bu məsələdə biz alp xizəksürmə növlərindən yalnız biri ilə məşğul oluruq: slalom. Bir sıra qapılar qoyularaq bir marşrut qurulur, bu qapılar iki dirəkdən ibarətdir. Xizəkçi hər qapını təşkil edən iki dirəyin arasından keçməlidir. Qalib, marşrutu ən az vaxtda tamamlayan və heç bir qapını qaçırmayan xizəkçidir.
Siz xizəksürməyə yeni başlamısınız, lakin artıq özünüzə 2018-ci il Qış Olimpiya Oyunlarında iştirak etməyi hədəf qoymusunuz, Madridin namizədliyini irəli sürəcəyi gözlənilir. Nəzəri təlimin bir hissəsi olaraq, sizdən başlanğıc nöqtəsi və bir sıra qapılar verildikdə, verilmiş nöqtədən başlayaraq hər qapıdan keçərək sonuncu qapıya çatana qədər minimum uzunluqlu yolu hesablayan bir proqram yazmağınız tələb olunur. Qapıların üfüqi olduğunu və ən yüksəkdən ən aşağıya doğru sıralandığını, yəni onlardan ardıcıl keçməli olduğunuzu qəbul edə bilərsiniz. Siz özünüzü bacarıqlı xizəkçi hesab edirsiniz, buna görə də nə qədər çətin olsa da, istənilən növ dönüşləri edə bilərsiniz və yeganə narahatlığınız yolun ümumi uzunluğunu minimuma endirməkdir.
Giriş verilənləri
Hər bir halın ilk sətiri qapıların sayını n (1 ≤ n ≤ 1 000) verir. Növbəti sətir iki onluq nöqtə ədədi, başlanğıc mövqeyinin Kartes koordinatları x və y ardıcıllıqla ehtiva edir. Daha sonra n sətir gəlir, hər biri üç onluq nöqtə ədədi ilə, y x_1 x_2, bu o deməkdir ki, növbəti qapı (x_1, y) ilə (x_2, y) arasında üfüqi bir xəttdir. x_1 < x_2 olduğunu təhlükəsiz qəbul edə bilərsiniz. y dəyərləri ciddi şəkildə azalan və başlanğıc mövqeyindən həmişə kiçikdir. Son qapı finiş xəttini təmsil edir. Bütün koordinatlar −500 000 ilə 500 000 arasında, daxil olmaqla, yerləşir. n üçün 0 dəyəri girişin sonunu bildirir. Hər bir haldan sonra boş bir sətir gəlir.
Çıxış verilənləri
Hər test halı üçün finiş xəttinə çatmaq üçün lazım olan minimum məsafəni bir sətirdə çıxarın. Cavabınız 10^{−7} nisbi və ya mütləq səhv daxilində dəqiq olmalıdır.