T - Покрытие
Если Вы когда-нибудь играли в Тетрис, вы должны знать, что одна из фигур выглядит так:
Мы будем называть эту фигуру Т-тетрамино. Тетрамино - это просто модное слово для связной геометрической фигуры, состоящей из 4 клеток. Отмеченная клетка будет называться центральной клеткой.
Манка рисует прямоугольную сетку с m рядами и n столбцами и записывает некоторое число в каждую клетку. Ряды таблицы пронумерованы от 0 до m - 1, столбцы от 0 до n - 1. Онатакже отмечает некоторые клетки как особые - например окрашивая их в красный цвет. После этого она просит Нику, свою подругу, расположить несколько T-тетрамино на сетке таким образом, чтобы выполнялись следующие условия:
Количество T-тетрамино должно быть таким же, как и особых клеток.
Для каждого T-тетрамино, его центральная клетка должна лежать на особой клетке.
Ни одна пара Т-тетрамино не должна перекрываться.
Все Т-тетрамино должны полностью лежать в нарисованной сетке. Обратите внимание, что существует 4 возможных расположения для каждого T-тетрамино
![Screenshot from 2019-12-28 11-57-15.png]
(https://static.e-olymp.com/content/75/7577ad99d73b38b9383f1efb5b6a0466648f222a.png)
Если условия не могут быть выполнены, Ника должна ответить 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)
Объяснения к первому примеру
