Путь через горы (малые ограничения)
Поверхность Земли в горной местности можно представить в виде ломаной линии. Вершины ломаной расположены в точках (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 ≤ 42); затем натуральное число K (1 ≤ K ≤ 23) - максимальное количество мостов; далее число 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}.
Выходные данные
Программа должна вывести одно число - минимальную длину пути, которую придется пройти магу (как по земле, так и по мостам). Ответ выведите с точностью 6 цифр после десятичной точки.