T - Covering

If you have ever played Tetris, you might know that one of the figures looks as follows:

We call this figure a T-tetromino. A tetromino is a connected geometric figure made of four cells. The cell marked with × is the center cell.

Manca draws a rectangular grid with $m$ rows and $n$ columns and writes a number into each cell. Rows are numbered from 0 to $m-1$, and columns from 0 to $n-1$. She also marks some cells as special, for example by painting them red. Then she asks her friend Nika to place T-tetrominoes on the grid under these conditions:

• The number of T-tetrominoes must equal the number of special cells. The center cell of each T-tetromino must lie on a special cell.
• No two T-tetrominoes may overlap.
• Every T-tetromino must lie completely inside the grid.

A T-tetromino has four orientations: ┬, ┴, ├, and ┤.

If the conditions cannot be met, Nika answers No. Otherwise, she finds a placement that maximizes the sum of the numbers in the cells covered by the T-tetrominoes, and tells Manca that maximum sum.

Write a program that helps Nika solve this puzzle.

The first line contains integers $m$ and $n$. Each of the following $m$ lines contains $n$ integers in the interval $[0, 1000]$. The $j$-th integer in the $i$-th line is the number written in the cell at row $i$ and column $j$.

The next line contains an integer $k$ with $k \in \{1, \ldots, mn\}$. Each of the following $k$ lines contains integers $r_i \in \{0, \ldots, m-1\}$ and $c_i \in \{0, \ldots, n-1\}$, the row and column of the $i$-th special cell. The list of special cells has no duplicates.

Print the maximum possible sum of the numbers in the cells covered by the T-tetrominoes. If no valid placement exists, print No.

$1 \le mn \le 10^6$