Dağlar vasitəsilə yol 2#814
Dağlıq bir bölgədə Yer səthini poliliniya kimi təsvir etmək olar. Bu poliliniyanın təpə nöqtələri \left(x_1, y_1\right), \left(x_2, y_2\right), \ldots, \left(x_N, y_N\right) nöqtələrində yerləşir; burada hər bir üçün x_i < x_{i+1}.
Bir dağ sehrbazı \left(x_1, y_1\right) nöqtəsində yerləşir və \left(x_N, y_N\right) nöqtəsinə çatmaq istəyir. Sehrbaz aşağıdakı şəkildə hərəkət edə bilər:
Yer səthi boyunca (verilmiş poliliniya üzrə) yeriməklə.
Havadakı iki poliliniya təpə nöqtəsini birləşdirən körpü yaradıb, onun üzərindən keçərək.
Körpü aşağıdakı tələblərə cavab verməlidir:
O, yalnız poliliniyanın təpə nöqtələrində başlaya və bitə bilər.
Yer altından (o cümlədən bir dağı tunel kimi keçərək) keçə bilməz, lakin bəzən Yer səthi ilə üst-üstə düşə bilər.
Hər bir körpünün uzunluğu -dan artıq ola bilməz.
Bütün istifadə olunan körpülərin uzunluqlarının cəmi -dən artıq ola bilməz.
Hər körpüdən keçdikdən sonra həmin körpü yox olur.
Sehrbazın \left(x_N, y_N\right) nöqtəsinə çatması üçün (istər yer səthi ilə, istər körpülərlə) getməli olduğu minimal məsafə nə qədərdir?
Giriş aşağıdakı kimidir:
Bir tam ədəd (2 \leq N \leq 64).
Bir tam ədəd (0 \leq R \leq 10000) — bir körpünün maksimum icazə verilən uzunluğu.
Bir tam ədəd (R \leq S \leq 10000) — körpülərin ümumi uzunluğunun maksimum cəmi.
Daha sonra cüt tam ədəd — \left(x_1, y_1\right), \left(x_2, y_2\right), \ldots, \left(x_N, y_N\right).
Bütün koordinatlar -dən böyük və ya kiçik olmayan tam ədədlərdir. Hər bir üçün 1 \leq i \leq N-1, x_i < x_{i+1}.
Bir ədəd çap edin — sehrbazın (poliliniya üzrə və körpülərlə) keçməli olduğu minimal yolun uzunluğunu. Cavabı dəqiq olaraq onluq vergüllə çap edin.
Nümunə 1