Dağlar vasitəsilə yol 2
Yer səthini dağlıq ərazidə qırıq xətt şəklində təsvir etmək olar. Bu qırıq xəttin zirvələri (x_1, y_1), (x_2, y_2), ..., (x_N, y_N) nöqtələrində yerləşir və burada x_i < x_i_{+1}. Dağ magı (x_1, y_1) nöqtəsində yerləşir və (x_N, y_N) nöqtəsinə çatmaq istəyir. O, yalnız piyada hərəkət edə bilər və Yer səthi boyunca, yəni qırıq xətt boyunca gəzə bilər. Həmçinin, havada körpü yarada bilər və onun üzərindən keçə bilər. Körpü qırıq xəttin iki zirvəsini birləşdirə bilər: körpü qırıq xəttin zirvəsində başlamalı və bitməlidir, yerin altında keçə bilməz (tunel ola bilməz), lakin yer səthinin müəyyən bir hissəsi boyunca keçə bilər. Körpünün uzunluğu R-dən çox ola bilməz. Mag ümumi uzunluğu K-dən çox olmayan körpülər qura bilər. Magın (x_N, y_N) nöqtəsinə çatmaq üçün keçməli olduğu ən kiçik məsafə nə qədərdir?
Giriş verilənləri
Proqram əvvəlcə təbii ədəd N (2 ≤ N ≤ 64); sonra tam ədəd R (0 ≤ R ≤ 10000) - bir körpünün mümkün olan maksimum uzunluğu; daha sonra tam ədəd S (R ≤ S ≤ 10000) - körpülərin maksimum cəmi uzunluğu oxumalıdır. Daha sonra koordinatlar (x_1, y_1), (x_2, y_2), ..., (x_N, y_N) verilir. Bütün koordinatlar tam ədədlərdir, modulu 10000-dən çox olmayan, bütün i üçün 1-dən N-1-ə qədər x_i < x_i_{+1} yerinə yetirilir.
Çıxış verilənləri
Proqram bir ədəd çıxarmalıdır - magın keçməli olduğu yolun minimum uzunluğu (həm yer, həm də körpülər üzrə). Cavabı 5 onluq dəqiqliklə çıxarın.