Description

If you have played Tetris, you should have seen the following shape:

We call it a T-shaped tetromino. Its center is marked by $\times$.

Manca drew a rectangular grid with $m$ rows and $n$ columns. Rows are numbered from $0$ to $m-1$, and columns are numbered from $0$ to $n-1$. She marked some cells in the grid as special cells. Then, she wants her friend Nika to help her place T-shaped tetrominoes according to the following rules:

• The number of special cells is the same as the number of T-shaped tetrominoes, and the center of each T-shaped tetromino must be on a special cell in the grid.
• T-shaped tetrominoes must not overlap.
• All parts of all tetrominoes must lie inside the grid.

Note that a T-shaped tetromino has four orientations: $\bot \top \vdash \dashv$.

If no arrangement exists, output No. Otherwise, find an arrangement that maximizes the sum of the numbers in the covered cells, and output this maximum value.

Input Format

The first line contains two integers $m,n$, representing the number of rows and the number of columns.

The next $m$ lines each contain $n$ integers. The $j$-th number in the $i$-th line (indexed from $0$) represents the value $a_{i,j}$ in the cell at row $i$ and column $j$.

The next line contains one integer $k$, representing the number of special cells.

The next $k$ lines each contain two integers $r_i,c_i$, representing the position of the $i$-th special cell.

Output Format

If an arrangement exists, output the maximum possible sum of the numbers in the covered cells. Otherwise, output No.

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

67

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

No

Hint

Explanation of Sample Input/Output 1

One optimal arrangement is as follows:

• The tetromino centered at $(1,1)$ is oriented as $\dashv$.
• The tetromino centered at $(2,2)$ is oriented as $\vdash$.
• The tetromino centered at $(3,4)$ is oriented as $\bot$.

Constraints and Notes

This problem uses bundled testdata and has 7 subtasks.

• Subtask 1 (5 points): $k\le 10^3$, and it is guaranteed that for all $i\ne j$, $\max(|r_i-r_j|,|c_i-c_j|)>2$.
• Subtask 2 (10 points): $k\le 10^3$, and it is guaranteed that for all $i\ne j$, if $\max(|r_i-r_j|,|c_i-c_j|)\le 2$, then $(r_i,c_i)$ and $(r_j,c_j)$ share an edge.
• Subtask 3 (10 points): $k\le 10^3$, and it is guaranteed that for all $i\ne j$, $\max(|r_i-r_j|,|c_i-c_j|)\ne 2$.
• Subtask 4 (10 points): All special cells are in the same row.
• Subtask 5 (15 points): $k\le 10$.
• Subtask 6 (20 points): $k\le 10^3$.
• Subtask 7 (30 points): No additional constraints.

For all testdata: $1\le k\le nm\le 10^6$, $a_{ij}\in[0,10^3]$, $r_i\in[0,m)$, $c_i\in[0,n)$.

Notes

The original problem is from: eJOI2019 Problem C. T - Covering.

The translation is from: LibreOJ。

Translated by ChatGPT 5