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]

(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,если не существует способа расставить их.

Ограничения

  • (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
Источник EJOI 2019 Day1