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

Шлях через гори

Шлях через гори

Ліміт часу 2 секунди
Ліміт використання пам'яті 64 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 (2N555); потім натуральне число K (1K256) - максимальну кількість мостів; далі число R (0R10000) - максимальну можливу довжину мосту. Далі координати (x_1, y_1), (x_2, y_2), ..., (x_N, y_N). Усі координати - цілі числа, які не перевищують по модулю 10000, для усіх i від 1 до N-1 виконується x_{i }< x_{i+1}.

Вихідні дані

Програма повинна вивести одне число - мінімальну довжину шляху, яку доведеться пройти магу (як по землі, так і по мостам). Відповідь виведіть з точністью 6 цифр після десяткової крапки.

Приклад

Вхідні дані #1
5 2 5
0 0
2 2
3 -1
4 1
5 0
Вихідні дані #1
6.4787086646190746
Автор Ілля Порубльов
Джерело Літня школа Севастополь 2013, Хвиля 1, День 2