Задача №860. Путь через горы

Поверхность Земли в горной местности можно представить в виде ломаной линии. Вершины ломаной расположены в точках (x1, y1), (x2, y2),…,(xN, yN), при этом xi<xi+1.

Обычный горный маг находится в точке (x1, y1) и хочет попасть в точку (xN, yN). При этом он может перемещаться только пешком. Он может ходить по поверхности Земли (т.е. вдоль ломаной). А может сотворить в воздухе мост и пройти по нему. Мост может соединять две вершины ломаной: мост не может начинаться и заканчиваться не в вершине ломаной, и мост не может проходить под землей (в том числе не может быть туннелем в горе), но мост может каким-то своим участком проходить по поверхности земли. Длина моста не может быть больше R. Суммарно маг может построить не более K мостов.

Какое наименьшее расстояние придется пройти магу, чтобы оказаться в точке (xN, yN).

Входные данные

Вводится сначала натуральное число N (2≤N≤100). Затем водится натуральное число K (1≤K≤100) — максимальное количество мостов. Далее вводится целое число R (0≤R≤10000) — максимальная возможная длина моста. Далее вводятся координаты (x1, y1), (x2, y2),…,(xN, yN). Все координаты – целые числа, не превышающие по модулю 10000, для всех i от 1 до N–1: xi<xi+1.

Выходные данные

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

Примеры

Входных данные

Выходные данные

5 2 5

0 0

2 2

3 -1

4 1

5 0

6.47871

9 2 3

1 2

2 1

3 3

5 -1

6 2

7 0

8 1

9 0

10 1

14.93498
Сдать: для сдачи задач необходимо войти в систему