Охоронець#3025
Компанія Bluewater Security надає охоронців для клієнтів із цінними речами. Bluewater з'ясувала, що клієнти хочуть розміщення охоронців так, щоб вони могли бачити всі цінності, лише повертаючи голову, а також щоб охоронці були розміщені особливо близько до особливо цінних предметів. Приклад схеми розташування вказано вище. Зараз ігноруйте три чорні точки. Різні місця позначені мітками та значеннями. Наприклад, точка A з координатами — місце предмета із цінністю . Місця зі значенням , як-от G, не містять цінного предмета. Прямі лінії на схемі означають коридори. Для спрощення коридори вважаються відрізками з нульовою шириною. Охоронець у точці перетину декількох коридорів може бачити й, відповідно, охороняти предмети на кожному з коридорів. Якби Bluewater замовили охоронців, їх можна було б розмістити у точках, позначених малими чорними точками. Охоронець, не розташований у вже позначеній точці, стоїть у . Щоб моделювати бажання розташовувати охоронців ближче до цінніших предметів, Bluewater обчислює ризик для цінності як добуток її цінності на мінімальну відстань до охоронця, що може бачити цей предмет. Навіть якщо охоронець знаходиться близько до предмета за кутом, він не впливає на ризик для цього предмета, оскільки не може бачити за кут. На наведеній схемі ризики для предметів такі: A: 4\times5=20, C: 4\times2.5=10, D: 2\times0=0, .... Найбільші ризики мають H: 50\times7.5=375 та I: 50\times7.5=375, тож максимальний ризик для будь-якого предмета становить . Для такого розміщення немає кращого варіанту для охоронців, який забезпечив би менший максимальний ризик, тож це розміщення мінімізує максимальний ризик. Bluewater хотіла б уміти повідомити будь-якому клієнту, що запросить певну кількість охоронців для певної схеми, який буде мінімізований максимальний ризик.
Вхід міститиме від одного до шістнадцяти наборів даних, за якими йде рядок, що містить лише . У кожному рядку дані подаються у вигляді токенів, розділених пропусками.
Перший рядок набору даних містить цілі числа , де — кількість заданих точок, — кількість коридорів, а — кількість охоронців для розміщення. Обмеження: 1 < p < 12, 0 < c < 12, 0 < g < 5.
Далі в наборі даних йдуть загалом груп по чотири токени, кожен складається з великої літери та трьох невід'ємних цілих чисел , що означає: точка із міткою містить предмет вартості . Якщо p \leq 6, усі ці групи наведені в одному рядку. Якщо p > 6, то сьома й наступні групи подаються в наступному рядку. Мітки — це послідовні літери від A. Усі числа менші за . Кожна точка унікальна. Значення v=0 означає, що в цій точці немає цінності. Кількість точок з цінностями буде не меншою за кількість охоронців.
Останній рядок набору даних містить рядків із літерами, по одному для кожного коридору. Кожен коридор задається літерами — мітками точок уздовж коридору, за порядком уздовж відрізка від одного кінця до іншого, включно з обома кінцями, усіма точками перетину з іншими коридорами і всіма точками на коридорі, де розташовані цінності. Кожна точка, наведена у наборі даних, буде лежати щонайменше на одному коридорі.
Для кожного набору даних має бути один рядок результату. Якщо охоронців недостатньо, щоб побачити всі цінності, виведіть too few guards. Інакше виведіть невід'ємне число , округлене до двох знаків після коми, де — це мінімальне значення з-поміж усіх розміщень охоронців максимальної "ризиковості" для цінних предметів.
Приклад 1