Вы недавно водили Фьорд?
Как многим из нас известно, западное побережье Скандинавии изобилует небольшими морскими заливами, называемыми фьордами. Фьорды имеют очень крутые склоны, и путешествие вдоль побережья становится довольно утомительным (хотя и захватывающим), поскольку дороги вынуждены изгибаться вокруг них. Комиссия по ускорению движения в Скандинавии через фьорды (FAST) решила справиться с этой проблемой, установив серию мостов через фьорды, чтобы сократить расстояния, которые необходимо преодолевать. Чтобы сэкономить, FAST использует заранее изготовленные мостовые блоки длиной 1 метр каждый, но из-за ограничений финансирования общая длина моста, который они могут построить, ограничена. Поэтому они хотят определить оптимальные места для установки мостов, которые позволят сэкономить наибольшую длину дороги. Например, если мост длиной 10 метров построен и сокращает 30 метров старой дороги, экономия составляет 20 метров. Чтобы упростить определение мест для установки мостов, FAST решила моделировать каждый фьорд как два отрезка, соединяющих три точки, как показано на рисунке ниже.
Все углы, образующие фьорды, конечно, меньше 180°. Более того, по соображениям безопасности каждый мост может пересекать не более одного фьорда.
Входные данные
Ввод для каждого тестового случая состоит из двух строк. Первая строка содержит два положительных целых числа n и m, указывающих количество фьордов и максимальную длину (в метрах) моста, который можно построить. Следующая строка содержит 2n+1 пар целочисленных координат для фьордов, где последняя координата для фьорда i служит первой координатой для фьорда i+1. Все координаты даны в метрах и находятся в диапазоне от -300000 до 300000. Максимальные значения для n и m составляют 50 и 3000 соответственно.
Ввод заканчивается строкой 0 0.
Выходные данные
Для каждого тестового случая выведите одну строку, содержащую номер случая, за которым следует длина использованного моста и общая экономия для оптимального размещения мостов, используя формат, показанный ниже. Все значения должны быть в метрах, а последнее число округлено до ближайшей сотой.