eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Путь через горы

Путь через горы

Ліміт часу 1 секунда
Ліміт використання пам'яті 256 MiB

Поверхность Земли в горной местности можно представить в виде ломаной линии. Вершины ломаной расположены в точках (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 (2N200); затем натуральное число K (1K100) - максимальное количество мостов; далее целое число R (0R10000) - максимальную возможную длину моста. Далее координаты (x_1, y_1), (x_2, y_2), ..., (x_N, y_N). Все координаты - целые числа, не превышающие по модулю 10000, для всех i от 1 до N-1 выполняется x_i < x_i_{+1}.

Вихідні дані

Программа должна вывести одно число - минимальную длину пути, которую придётся пройти магу (как по земле, так и по мостам). Ответ выведите с точностью 5 цифр после десятичной точки.

Приклад

Вхідні дані #1
5 2 5
0 0
2 2
3 -1
4 1
5 0
Вихідні дані #1
6.47871