eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

T - Покрытие

T - Покрытие

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Если вы когда-нибудь играли в Тетрис, вы должны знать, что одна из фигур выглядит так:

covering.PNG

Мы будем называть эту фигуру Т-тетрамино; тетрамино — это просто модное слово длясвязной геометрической фигуры, состоящей из 4 клеток. Клетка, отмеченная , будетназываться центральной клеткой.Манка рисует прямоугольную сетку с m рядами и n столбцами и записывает некоторое числов каждую клетку. Ряды таблицы пронумерованы от 0 до m-1 , и столбцы от 0 до n-1 . Онатакже отмечает некоторые клетки как особые, например, окрашивая их в красный цвет. Послеэтого она просит Нику, свою подругу, расположить несколько T-тетрамино на сетке такимобразом, чтобы выполнялись следующие условия:

  • Количество T-тетрамино должно быть таким же, как и особых клеток.

  • Для каждого T-тетрамино, его центральная клетка должна лежать на особой клетке.

  • Ни одна пара Т-тетрамино не должна перекрываться.

  • Все Т-тетрамино должны полностью лежать в нарисованной сетке. Обратите внимание, что существует 4 возможных расположения для каждого T-тетрамино

    Screenshot from 2019-12-28 11-57-15.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,если не существует способа расставить их.

####Ограничения

  • (1mn10^6 )

####Объяснения к первому примеру

Screenshot from 2019-12-28 11-55-50.png

Приклад

Вхідні дані #1
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​
Вихідні дані #1
67
Вхідні дані #2
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​
Вихідні дані #2
No