Dağlar vasitəsilə yol
Yer səthini dağlıq ərazidə qırıq xətt kimi 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}. Adi dağ sehrbazı (x_1, y_1) nöqtəsindədir 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) gedə bilər. Bundan əlavə, sehrbaz 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ından keçə bilməz (tunel ola bilməz), lakin körpü öz hissəsi ilə yer səthindən keçə bilər. Körpünün uzunluğu R-dən çox ola bilməz. Sehrbaz ümumilikdə K-dən çox körpü qura bilməz. Körpüdən keçdikdən sonra o (körpü) havada yox olur. Sehrbazı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 ≤ 200) oxumalıdır; sonra təbii ədəd K (1 ≤ K ≤ 100) - maksimum körpü sayı; daha sonra tam ədəd R (0 ≤ R ≤ 10000) - körpünün maksimum mümkün uzunluğu. Daha sonra koordinatlar (x_1, y_1), (x_2, y_2), ..., (x_N, y_N). 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} şərti ödənilir.
Çıxış verilənləri
Proqram bir ədəd çıxarmalıdır - sehrbazın keçməli olduğu yolun minimum uzunluğu (həm yer üzərində, həm də körpülər üzərində). Cavabı 5 onluq dəqiqliklə çıxarın.