T - Покриття#9047

T - Покриття

1 секунда

128 мегабайтів

Легка

Якщо ви коли-небудь грали в Тетріс, ви, напевно, знаєте, що одна з фігур виглядає так:

Ми будемо називати цю фігуру Т-тетраміно. Тетраміно — це просто модне слово для зв'язної геометричної фігури, що складається з $4$ клітинок. Позначена клітинка буде називатися центральною клітинкою.

Манка малює прямокутну сітку з $m$ рядками і $n$ стовпцями і записує деяке число в кожну клітинку. Рядки таблиці пронумеровані від $0$ до $m - 1$ m - 1, стовпці від $0$ до $n - 1$ n - 1. Вона також позначає деякі клітинки як особливі — наприклад, фарбуючи їх у червоний колір. Після цього вона просить Ніку, свою подругу, розташувати кілька T-тетраміно на сітці так, щоб виконувалися наступні умови:

Кількість T-тетраміно повинна дорівнювати кількості особливих клітинок.
Для кожного T-тетраміно, його центральна клітинка повинна лежати на особливій клітинці.
Жодна пара Т-тетраміно не повинна перекриватися.
Усі Т-тетраміно повинні повністю лежати в межах намальованої сітки. Зверніть увагу, що існує $4$ можливих орієнтації для кожного T-тетраміно.

Якщо умови не можуть бути виконані, Ніка повинна відповісти No; якщо вони виконувані, вона повинна знайти таке розташування T-тетраміно, щоб максимізувати суму чисел у клітинках, покритих T-тетраміно. У цьому випадку вона повинна повідомити Манці максимальну суму покритих T-тетраміно клітинок. Напишіть програму, щоб допомогти Ніці вирішити цю задачу.

Вхідні дані

Перший рядок містить два цілих числа $m$ і $n$ — висоту і ширину таблиці. Наступні $m$ рядків містять по $n$ цілих чисел у діапазоні від $0$ до $1000$ . $j$ -е ціле число в $i$ -му рядку відповідає числу, записаному в $j$ -й клітинці $i$ -го рядка сітки. Наступний рядок містить число $k$ ( $1 \leq k \leq m \cdot n$ 1 \leq k \leq m \cdot n) — кількість особливих клітинок у таблиці. Кожен з наступних рядків містить по два числа $r_{i}$ r_i і $c_{i}$ c_i, де $r_{i}$ r_i ( $0 \leq r_{i} \leq m - 1$ 0 \leq r_i \leq m-1) і $c_{i}$ c_i ( $0 \leq c_{i} \leq n - 1$ 0 \leq c_i \leq n-1) — номер рядка і стовпця $i$ -ої особливої клітинки, відповідно. Гарантовано, що всі координати особливих клітинок унікальні.

$1 \leq mn \leq 1 0^{6}$ 1 \leq mn \leq 10^6

Вихідні дані

Виведіть максимально можливу суму чисел, покритих T-тетраміно клітинками, або No, якщо не існує способу розставити їх.

Приклади

Приклад 1

Приклад 2

Примітка

Пояснення до першого прикладу: