Охоронець
Компанія Bluewater Security надає охоронців для клієнтів з цінними речами. Bluewater виявила, що клієнти хочуть, щоб охоронці були розміщені так, щоб вони могли бачити всі цінності, просто повернувши голову, і також прагнуть, щоб охоронці були розташовані якомога ближче до особливо цінних предметів. Зразок плану сайту показаний вище. Ігноруйте три чорні точки поки що. Різні місця позначені та мають значення. Наприклад, місце A з координатами (0,8) є позицією предмета зі значенням 4. Місця, що показують значення 0, як G, не мають цінного предмета. Прямі лінії вказують на коридори. Для простоти, коридори моделюються як відрізки ліній з нульовою шириною. Охоронець на точці перетину кількох коридорів може бачити і, отже, охороняти предмети на кожному з коридорів. Якщо Bluewater було б найнято для забезпечення 3 охоронців, вони могли б вибрати розмістити їх на позиціях, позначених маленькими чорними точками. Охоронець, що не знаходиться на вже позначеній позиції, знаходиться на (15.5, 6). Щоб змоделювати бажання, щоб охоронці були ближче до предметів з вищою цінністю, Bluewater обчислює ризик для цінного предмета як значення предмета, помножене на мінімальну відстань до охоронця, який може бачити предмет. Навіть якщо охоронець близько до предмета, який знаходиться за рогом, цей охоронець не впливає на ризик для предмета, оскільки охоронець не може бачити за ріг. На показаній діаграмі ризики для предметів такі: A: 4x5=20, C: 4x2.5=10, D: 2x0=0, .... Найбільші ризики для H: 50x7.5=375 і I: 50x7.5=375, тому максимальний ризик для будь-якого предмета становить 375. З цим планом сайту жодне розташування 3 охоронців не забезпечить нижчий максимальний ризик, тому це розташування 3 охоронців мінімізує максимальний ризик. Bluewater хотіла б мати можливість сказати будь-якому клієнту, який запитує певну кількість охоронців для певного плану сайту, яким буде мінімізований максимальний ризик.
Вхідні дані
Вхідні дані складатимуться з одного до шістнадцяти наборів даних, за якими йде рядок, що містить лише 0. На кожному рядку дані складатимуться з розділених пробілами токенів.
Перший рядок набору даних містить цілі числа p c g, де p — кількість вказаних точок, c — кількість коридорів, і g — кількість охоронців, яких потрібно розмістити. Обмеження: 1< p < 12; 0 < c < 12; 0 < g < 5.
Далі в наборі даних йдуть загалом p груп з чотирьох токенів, кожна з яких складається з великої літери та трьох невід'ємних чисел L x y v, що вказують на точку (x, y) з міткою L, яка містить предмет зі значенням v. Якщо p не більше 6, ці групи будуть на одному рядку. Якщо p більше 6, то сьома і подальші групи будуть на наступному рядку. Мітки будуть послідовними літерами, починаючи з A. Усі числа менші за 1000. Кожна з точок унікальна. Значення 0 для v означає, що там немає цінного предмета. Кількість місць з цінними предметами буде принаймні такою ж великою, як кількість охоронців.
Останній рядок набору даних містить c рядків літер, по одному для кожного коридору. Для кожного коридору літери є мітками для точок уздовж коридору, у порядку вздовж відрізка лінії від одного кінця до іншого, включаючи обидва кінці, всі точки перетину з іншими коридорами та всі місця на коридорі з цінним предметом. Кожна з точок, наведених у наборі даних, буде лежати принаймні на одному з коридорів.
Вихідні дані
Для кожного набору даних є один рядок виходу. Якщо охоронців недостатньо, щоб бачити всі цінності, рядок буде "too few guards". В іншому випадку рядок буде містити беззнакове число r, округлене до двох знаків після коми, де r — це мінімальне значення серед усіх розміщень g охоронців максимального "ризику" для цінностей.