Задачі
Візерунок
Візерунок
В кімнаті вирішили зробити підлогу з паркету. Причому є задумка викласти на підлозі деякий візерунок.
Плитки паркету, якими викладується підлога кімнати, складаються з квадратиків \textbf{1}x\textbf{1}, кожен з яких може бути або білим, або чорним. У свою чергу, кімната має розміри \textbf{N}x\textbf{M}. На плані кімнати вказано, який квадрат кімнати якого кольору повинен бути.
Існує декілька форм паркетних плиток:
\includegraphics{https://static.e-olymp.com/content/b0/b028942bf8792935a7ea1117142987dc7fb0897e.jpg}
Квадратики однієї паркетної плитки можуть бути пофарбовані по-різному. Може існувати декілька типів плиток однакової форми, але зафарбованих по-різному. Плитки різних типів можуть мати різну вартість. Кількість плиток кожного типу не обмежена. Плитки дозволяється як завгодно повертати (на кути, кратні \textbf{90} градусам). Не дозволяється розламувати плитки, а також класти їх лицевою стороною донизу.
У початковому стані якась частина підлоги може вже бути викладена плиткою.
Потрібно визначити мінімальну вартість плитки, необхідної для того, щоб замостити частину кімнати, що залишилась.
\InputFile
У першому рядку вхідного файлу записано три числа: \textbf{N}, \textbf{M} (розміри кімнати) і \textbf{K} (кількість доступних видів плитки). \textbf{1} <= \textbf{N}, \textbf{M} <= \textbf{8}, \textbf{1} <= \textbf{K}\textit{ <=} \textbf{10}. Далі йде опис бажаної розфарбовки підлоги. Опис являє собою \textbf{N} рядків по \textbf{M} чисел у кожному, де \textbf{0} позначає білий колір, \textbf{1} --- чорний, \textbf{2} --- те, что квадрат вже викладено плиткою. В останніх \textbf{K} рядках знаходиться опис доступних типів плитки у наступному форматі:
<форма> <вартість> <колір>
<Форма> --- це число від \textbf{1} до \textbf{4}, що описує форму плитки (див. рисунок вище)
<Вартість> --- це натуральне число, яке не перевищує \textbf{10000}, що задає вартість одніє плитки такого типу
<Колір> --- це від одного до трьох чисел \textbf{0} або \textbf{1}. Кількість чисел співпадає з кількістю квадратиків, з яких складається плитка. Числа задають кольори квадратиків плитки у тому ж порядку, в якому квадратики пронумеровані на рисунку.
\OutputFile
У вихідний файл виведіть єдине число --- мінімальну вартість укладки або \textbf{--1}, якщо належним чином покласти плитку неможливо.
Вхідні дані #1
4 3 3 2 2 2 2 0 0 2 1 2 2 2 2 2 10 0 0 1 5 1 4 6 0 0 1
Вихідні дані #1
15