Чи Керували Ви Фіордом Нещодавно?#2681
Як відомо більшості, західне скандинавське узбережжя містить багато невеликих морських заток, відомих як фіорди. Фіорди мають дуже круті береги, що ускладнює подорожування уздовж узбережжя (хоча і захоплює дух), оскільки дороги повинні петляти навколо них. Комісія прискореного скандинавського руху через фіорди (FAST) вирішила вирішити цю проблему, збудувавши серію мостів через фіорди для скорочення довжини маршрутів. Для економії коштів FAST використовує попередньо виготовлені секції мосту довжиною метр кожна, але у зв'язку з обмеженим фінансуванням загальна довжина мостів також обмежена. Тому вони хотіли б визначити оптимальні місця для встановлення мостів, щоб максимізувати економію на загальній довжині доріг. Наприклад, якщо міст довжиною метрів дозволяє скоротити метрів старої дороги, економія становить метрів. Щоб спростити задачу визначення місць для мостів, FAST вирішила моделювати кожен фіорд як два відрізки прямих, що з'єднують три точки, як показано на рисунку нижче.
Усі кути, які формують фіорди, менші за 180^{\circ}. Крім того, з міркувань безпеки кожен міст може перекривати не більше одного фіорду.
Вхід для кожного тестового випадку складається з двох рядків. Перший рядок містить два додатних цілих числа і , що означають кількість фіордів і максимальну загальну довжину мостів (у метрах), яку можна збудувати. Наступний рядок містить 2n+1 пар цілих координат для фіордів, причому остання координата для фіорду також є першою координатою для фіорду i+1. Усі координати задано в метрах та знаходяться в діапазоні від до . Максимальні значення для і становлять та відповідно.
Вхід закінчується рядком, що містить .
Для кожного тестового випадку виведіть один рядок, що містить номер випадку, загальну використану довжину мостів і сумарну економію для оптимального розміщення мостів у форматі, наведеному нижче. Усі значення мають бути в метрах, а показник економії округлюється до сотих.
Приклад 1