eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Прибирання снігу

Прибирання снігу

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Взимку, коли дні стають коротшими, а ночі - довшають необхідно задуматися про прибирання вулиць від снігу. Але бюджет нашого міста дуже малий тому ми маємо лише один снігохід. Незважаючи на це, дороги повинні бути прочищені. Отже кожного разу, коли випадає багато снігу, вночі снігохід нашого міста виїжджає зі свого гаражу і об’їжджає все місто, прочищаючи дороги. Який мінімальний час знадобиться снігоходу, щоб очистити усі проїжджі смуги усіх доріг і повернутися назад?

При цьому відомо, що:

  • Снігохід може прочищати лише одну проїзджу смугу дороги за один прохід.

  • Всі дороги прямі з однією смугою руху в кожному напрямі.

  • Снігохід може повертати на будь-якому перехресті в будь-яку сторону, а також може розвернутися в тупику.

  • Під час чищення снігу снігохід рухається зі швидкістю 20 км/год, та зі швидкістю 50 км/год по вже прочищеній дорозі. Можливість проїхати всі дороги завжди існує.

Вхідні дані

Перший рядок містить два числа x та y (-30000x, y30000) - координати ангару (в метрах), звідки починає свій рух снігохід. Далі координати (в метрах) початку та кінця вулиць (по 4 числа). У місті може бути до 100 вулиць.

Вихідні дані

Виведіть час в годинах і хвилинах, необхідний для очищення усіх доріг та повернення до ангару. Час слід округлити до найближчої хвилини.

Приклад

Вхідні дані #1
0 0
0 0 10000 10000
5000 -10000 5000 10000
5000 10000 10000 10000
Вихідні дані #1
3:55