T - Покрытие
T - Покрытие
Если вы когда-нибудь играли в Тетрис, вы должны знать, что одна из фигур выглядит так:
Мы будем называть эту фигуру Т-тетрамино; тетрамино — это просто модное слово длясвязной геометрической фигуры, состоящей из 4 клеток. Клетка, отмеченная , будетназываться центральной клеткой.Манка рисует прямоугольную сетку с m рядами и n столбцами и записывает некоторое числов каждую клетку. Ряды таблицы пронумерованы от 0 до m-1 , и столбцы от 0 до n-1 . Онатакже отмечает некоторые клетки как особые, например, окрашивая их в красный цвет. Послеэтого она просит Нику, свою подругу, расположить несколько T-тетрамино на сетке такимобразом, чтобы выполнялись следующие условия:
Количество T-тетрамино должно быть таким же, как и особых клеток.
Для каждого T-тетрамино, его центральная клетка должна лежать на особой клетке.
Ни одна пара Т-тетрамино не должна перекрываться.
Все Т-тетрамино должны полностью лежать в нарисованной сетке. Обратите внимание, что существует 4 возможных расположения для каждого T-тетрамино
Если условия не могут быть выполнены, Ника должна ответить No; если они выполнимы, онадолжна найти такое расположение T-тетрамино, чтобы максимизировать сумму чисел вклетках, покрытых T-тетрамино. В этом случае она должна сообщить Манке максимальнуюсумму покрытых T-тетрамино клеток.Напишите программу, чтобы помочь Нике решить эту задачу.
####Входные данныеПервая строка входных данных содержит два целых числа m и n — высоту и ширинутаблицы. Следующие m строк содержат по n целых чисел в интервале [0,1000] . j-е целоечисло в i-й строке соответствует числу,записанному в j-й клетке i-го ряда сетки.Следующая строка содержит число k[1,.....,m*n] — количество особых клеток в таблице. Каждая из последующих строк содержит по два числа r[i]
и c[i]
, r[i]
[0,....,m-1] и c[i]
[0,....,n-1] — номер строки и столбца i-ой особой клетки,соответственно. Гарантируется,что все координаты особых клеток уникальны.
####Выходные данныеВыведите максимально возможную сумму чисел,покрытых T-тетрамино клеток,либо No,если не существует способа расставить их.
####Ограничения
(1 ≤ mn ≤
10^6
)
####Объяснения к первому примеру
Приклад
5 6 7 3 8 1 0 9 4 6 2 5 8 3 1 9 7 3 9 5 2 6 8 4 5 7 3 8 2 7 3 6 3 1 1 2 2 3 4
67
5 6 7 3 8 1 0 9 4 6 2 5 8 3 1 9 7 3 9 5 2 6 8 4 5 7 3 8 2 7 3 6 3 1 1 2 2 3 3
No