Узор

В комнате решили сделать паркетный пол. Причем есть задумка выложить на полу некоторый узор. Плитки паркета, которыми выкладывается пол комнаты, состоят из квадратиков 1×1, каждый из которых может быть либо белым, либо черным. В свою очередь, комната имеет размеры N×M. На плане комнаты указано, какой квадрат комнаты какого цвета должен быть. Существует несколько форм паркетных плиток:

Квадратики одной паркетной плитки могут быть окрашены по-разному. Может существовать несколько типов плиток одинаковой формы, но окрашенных по-разному. Плитки разных типов могут иметь разную стоимость. Количество плиток каждого типа не ограничено. Плитки разрешается как угодно поворачивать (на углы, кратные 90 градусам). Не разрешается разламывать плитки, а также класть их лицевой стороной вниз.

Изначально, какая-то часть пола может уже быть выложена плиткой. Требуется определить минимальную стоимость плитки, необходимой для того, чтобы замостить оставшуюся часть комнаты.

Входные данные

В первой строке входного файла INPUT.TXT записаны три числа: N, M (размеры комнаты) и K (количество доступных видов плитки). 1 ≤ N ≤ 8, 1 ≤ M ≤ 8, 1 ≤ K ≤ 10. Далее идет описание желаемой раскраски пола. Описание представляет собой N строчек по M чисел в каждой, где 0 обозначает белый цвет, 1 — черный, 2 — то, что квадрат уже выложен плиткой. В последних K строчках находятся описания доступных типов плитки в следующем формате:

<форма> <стоимость> <окраска>

<Форма> — это число от 1 до 4, описывающее форму плитки (см. рисунок выше)

<Стоимость> — это натуральное число, не превосходящее 10000, задающее стоимость одной плитки такого типа

<Окраска> — это от одного до трех чисел 0 или 1. Количество чисел совпадает с количеством квадратиков, из которых состоит плитка. Числа задают цвета квадратиков плитки в том порядке, в каком квадратики пронумерованы на рисунке.

Выходные данные

В выходной файл OUTPUT.TXT выведите единственное число — минимальную стоимость укладки или –1, если требуемым образом уложить плитку невозможно.

Пример

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]