Поверхность Земли в горной местности можно представить в виде ломаной линии. Вершины ломаной расположены в точках (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≤100). Затем водится натуральное число K (1≤K≤100) — максимальное количество мостов. Далее вводится целое число R (0≤R≤10000) — максимальная возможная длина моста. Далее вводятся координаты (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
|
6.47871
|
|
2
|
9 2 3
1 2
2 1
3 3
5 -1
6 2
7 0
8 1
9 0
10 1
|
14.93498
|