Шлях через гори 2
Поверхню Землі в гірській місцевості можна уявити як ламану лінію. Вершини цієї ламаної знаходяться в точках (x_1, y_1), (x_2, y_2), ..., (x_N, y_N), причому x_i < x_i_{+1}. Звичайний гірський маг перебуває в точці (x_1, y_1) і прагне дістатися до точки (x_N, y_N). Він може пересуватися лише пішки, ходячи по поверхні Землі (тобто вздовж ламаної), або створюючи в повітрі міст, по якому може пройти. Міст може з'єднувати дві вершини ламаної: він не може починатися і закінчуватися не у вершині ламаної, і не може проходити під землею (включаючи тунелі в горах), але може частково проходити по поверхні землі. Довжина мосту не повинна перевищувати R. Загалом маг може побудувати мости загальною довжиною не більше K. Після проходження мосту, він (міст) зникає. Яку найменшу відстань потрібно пройти магу, щоб дістатися до точки (x_N, y_N)?
Вхідні дані
Програма повинна спочатку прочитати натуральне число N (2 ≤ N ≤ 64); потім ціле число R (0 ≤ K ≤ 10000) - максимально допустиму довжину одного мосту; далі ціле число S (R ≤ S ≤ 10000) - максимальну загальну довжину мостів. Далі йдуть координати (x_1, y_1), (x_2, y_2), ..., (x_N, y_N). Усі координати - цілі числа, що не перевищують за модулем 10000, для всіх i від 1 до N-1 виконується x_i < x_i_{+1}.
Вихідні дані
Програма повинна вивести одне число - мінімальну довжину шляху, яку доведеться пройти магу (як по землі, так і по мостах). Відповідь виведіть з точністю 5 цифр після десяткової точки.