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

Вхідні дані

Програма має спочатку зчитати рядок з трьома цілими числами ~N~ (~2\leqslant N\leqslant 555~, кількість вершин ламаної), ~K~ (~1\leqslant K\leqslant 256~, максимальна кількість мостів) та ~R~ (~0\leqslant R\leqslant 10000~, максимальна можлива довжина мосту). Далі слід зчитати координати ~(x_1,y_1)~, ~(x_2,y_2)~, ..., ~(x_N,y_N)~, кожна пара в окремому рядку. Усі координати — цілі числа, що не перевищують за модулем ~10000~, для всіх ~i~ від ~1~ до ~N-1~ виконується ~x_i<x_{i+1}~.</p>

Результати

Програма має вивести одне дійсне число — мінімальну довжину шляху, яку доведеться пройти магу (як по землі, так і по мостам). Відповідь виведіть із тією точністю, яку забезпечує стандартне виведлення, не округлюючи. Зараховувати відповідь буде, якщо абсолютна або відносна похибка (хоча б одна з двох) не перевищуватиме ~10^{-12}~.

Приклад

Вхід

5 2 5
0 0
2 2
3 -1
4 1
5 0

Результат

6.4787086646190746