Візерунок
В кімнаті вирішили зробити підлогу з паркету. Причому є задумка викласти на підлозі деякий візерунок.
Плитки паркету, якими викладується підлога кімнати, складаються з квадратиків 1x1, кожен з яких може бути або білим, або чорним. У свою чергу, кімната має розміри NxM. На плані кімнати вказано, який квадрат кімнати якого кольору повинен бути.
Існує декілька форм паркетних плиток:
Квадратики однієї паркетної плитки можуть бути пофарбовані по-різному. Може існувати декілька типів плиток однакової форми, але зафарбованих по-різному. Плитки різних типів можуть мати різну вартість. Кількість плиток кожного типу не обмежена. Плитки дозволяється як завгодно повертати (на кути, кратні 90 градусам). Не дозволяється розламувати плитки, а також класти їх лицевою стороною донизу.
У початковому стані якась частина підлоги може вже бути викладена плиткою.
Потрібно визначити мінімальну вартість плитки, необхідної для того, щоб замостити частину кімнати, що залишилась.
Вхідні дані
У першому рядку вхідного файлу записано три числа: N, M (розміри кімнати) і K (кількість доступних видів плитки). 1 <= N, M <= 8, 1 <= K <= 10. Далі йде опис бажаної розфарбовки підлоги. Опис являє собою N рядків по M чисел у кожному, де 0 позначає білий колір, 1 — чорний, 2 — те, что квадрат вже викладено плиткою. В останніх K рядках знаходиться опис доступних типів плитки у наступному форматі:
<форма> <вартість> <колір>
<Форма> — це число від 1 до 4, що описує форму плитки (див. рисунок вище)
<Вартість> — це натуральне число, яке не перевищує 10000, що задає вартість одніє плитки такого типу
<Колір> — це від одного до трьох чисел 0 або 1. Кількість чисел співпадає з кількістю квадратиків, з яких складається плитка. Числа задають кольори квадратиків плитки у тому ж порядку, в якому квадратики пронумеровані на рисунку.
Вихідні дані
У вихідний файл виведіть єдине число — мінімальну вартість укладки або –1, якщо належним чином покласти плитку неможливо.