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