H. Автобусы и интранет
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В городе запустили автобусный маршрут, представляющий собой замкнутую ломаную на плоскости, все звенья которой параллельны осям координат. На маршруте будет работать m автобусов, двигающихся по циклу вдоль ломаной в одном направлении с одинаковой постоянной скоростью (временем остановок автобусов в рамках данной задачи можно пренебречь).

Автобусы начинают движение по маршруту в первой вершине ломаной с равными промежутками. Пусть T — это время, за которое один автобус проезжает по кругу весь маршрут. Тогда автобус 1 начинает движение в момент времени 0, автобус 2 — в момент времени T / m, третий — в момент времени 2T / m, и т.д.; наконец, автобус m стартует в момент (m - 1)T / m. Таким образом, интервалы между всеми парами соседних автобусов (в том числе, между последним и первым) одинаковы.

Автобусы могут обмениваться информацией при помощи беспроводных передатчиков одинаковой мощности. Если мощность передатчиков на автобусах равна D, то обмен информацией возможен между автобусами на расстоянии D или меньше.

Кроме этого, автобусы оснащены распределенной системой слежения за маршрутом. Для того, чтобы все автобусы двигались строго по графику, система должна периодически синхронизировать данные на всех автобусах. В момент синхронизации автобус 1 обменивается информацией с автобусом 2, автобус 2 с автобусом 3, и т.д., кроме этого, автобус m обменивается информацией с автобусом 1.

Вам, как сотруднику аналитического отдела, поставили задачу найти минимальное значение D, при котором синхронизацию возможно проводить хотя бы время от времени.

Входные данные

В первой строке записано два целых числа n и m (2 ≤ n, m ≤ 105) — количество вершин ломаной и количество автобусов соответственно.

Следующие n строк описывают вершины ломаной в порядке ее обхода. Каждая из этих строк содержит два целых числа xi, yi ( - 1000 ≤ xi, yi ≤ 1000) — координаты очередной вершины.

Гарантируется, что каждое звено ломаной (в том числе, между последней и первой вершиной) параллельно одной из осей координат. Кроме этого, никакие две последовательные вершины ломаной не совпадают. Ломаная может иметь самопересечения и проходить по одному отрезку несколько раз.

Выходные данные

Выведите одно вещественное число — ответ на задачу. Ответ будет принят, если абсолютная или относительная погрешность не превосходит 10 - 6.

Примеры
Входные данные
4 2
0 0
0 1
1 1
1 0
Выходные данные
1.000000000
Входные данные
2 2
0 0
1 0
Выходные данные
0.000000000
Примечание

Пусть все автобусы проезжают 1 единицу расстояния в секунду. В первом примере, через 0.5 секунды автобусы окажутся на расстоянии 1, поэтому можно выбрать D = 1.

Во втором примере, через 0.5 секунды оба автобуса окажутся в точке (0.5, 0), поэтому можно выбрать D = 0.