Шлях через гори 2#814
Поверхню Землі в гірській місцевості можна зобразити ламаною лінією. Вершини цієї ламаної знаходяться в точках \left(x_1, y_1\right), \left(x_2, y_2\right), \ldots, \left(x_N, y_N\right), де для кожного виконується x_i < x_{i+1}.
Гірський маг знаходиться у точці \left(x_1, y_1\right) та бажає дістатися до \left(x_N, y_N\right). Маг може пересуватися:
По поверхні Землі (по заданій ламаній).
Створюючи міст у повітрі, що з'єднує дві вершини ламаної, і йдучи по ньому.
Міст повинен відповідати таким умовам:
Він має починатися та закінчуватися у вершинах ламаної.
Він не може проходити під землею (у тому числі як тунель крізь гору), але може деякий час збігатися з поверхнею Землі.
Довжина одного моста не може перевищувати .
Сумарна довжина всіх використаних мостів не може перевищувати .
Після переходу через міст, він зникає.
Яка мінімальна відстань, яку має пройти маг (по поверхні та по мостах), щоб дістатися до точки \left(x_N, y_N\right)?
Вхідні дані містять:
Одне ціле число (2 \leq N \leq 64).
Одне ціле число (0 \leq R \leq 10000) — максимальна можлива довжина одного моста.
Одне ціле число (R \leq S \leq 10000) — максимальна сумарна довжина всіх мостів.
Далі йде пар цілих чисел: \left(x_1, y_1\right), \left(x_2, y_2\right), \ldots, \left(x_N, y_N\right).
Усі координати — цілі числа з абсолютним значенням не більше . Для кожного від до N-1 виконується x_i < x_{i+1}.
Виведіть одне число — мінімальну довжину шляху, яку має пройти маг (по ламаній і по мостах), щоб дістатися \left(x_N, y_N\right). Відповідь виведіть з точно знаками після десяткової крапки.
Приклад 1