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)
Пояснення до першого прикладу
