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