В кімнаті вирішили зробити підлогу з паркету. Причому є задумка викласти на підлозі деякий візерунок. Плитки паркету, якими викладується підлога кімнати, складаються з квадратиків \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}, якщо належним чином покласти плитку неможливо.