Операція: Купець Буріней
Маленькі дівчатка та хлопчики на суднах також заслуговують на моторошне Різдво! Але доставляти подарунки рухомим цілям може бути справжньою морокою. Проблема в тому, що ви повинні летіти на своїх санях-труні туди, де судно буде, а не туди, де воно зараз. Король Гарбузів попросив вас написати програму, яка допоможе йому в цьому, і, маючи набір суден, спланувати маршрут, який займе мінімальну кількість часу для виконання.
Вам будуть надані початкові координати саней і кожного судна, на якому є діти. Кожне судно постійно рухається в напрямку та зі швидкістю, вказаною вектором швидкості (v_x, v_y), тобто через 1 годину воно пройде v_x км у напрямку x і v_y км у напрямку y (v_x та v_y можуть бути від'ємними). Довжина вектора є швидкістю. Сани Джека здатні рухатися з постійною швидкістю в будь-якому напрямку (припустимо, що прискорення та уповільнення є миттєвими). Джек повинен приземлитися на кожному судні хоча б раз, і на кожній зупинці потрібно 5 хвилин, щоб розвантажити подарунки. Сани можуть вмістити достатньо подарунків для всіх дітей без необхідності повертатися до Гарбузового Міста. Усі координати мають одиниці км, а всі швидкості та швидкості мають одиниці км/год.
Знайдіть найкоротший час, за який Джек зможе доставити подарунки на кожне судно і повернутися до початкового місця.
Вхідні дані
Вхід складається з кількох випадків. Кожен випадок починається з рядка, що містить ціле число N (1≤ N ≤ 8), яке вказує кількість суден. Наступні N рядків містять 4 цілі числа, розділені пробілом: початкові координати (x,y) i-го судна та його вектор швидкості. Останній рядок кожного випадку містить 3 цілі числа, що вказують початкові координати (x, y) саней та швидкість саней. Кінець введення позначається випадком, що починається з N = 0, і цей останній випадок не повинен оброблятися. Усі вхідні цілі числа мають абсолютне значення не більше 1000. Ви можете припустити, що сани рухаються з більшою швидкістю, ніж кожне судно. Зверніть увагу, що шляхи суден можуть перетинатися між собою або навіть з початковим місцем розташування саней, але капітани зроблять лише незначні корекції курсу, щоб уникнути зіткнень, тому вам не потрібно це враховувати.
Вихідні дані
Для кожного випадку надрукуйте його номер, двокрапку, а потім мінімальний час, необхідний для завершення доставки у форматі:
Випадок a: b година(годин) c хвилина(хвилин) d секунда(секунд)
де a, b, c, d є відповідними невід'ємними цілими числами, а c та d не перевищують 59. Час слід округлити до наступної секунди.