Шлях через гори (малі обмеження)
Поверхню Землі у гірській місцевості можна подати у вигляді ламаної лінії. Вершини ламаної розміщені у точках (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 цифр після десяткової крапки.