T - Covering
If you've ever played Tetris, you're likely familiar with one of its pieces that looks like this:
We'll refer to this piece as a T-tetromino. A tetromino is a connected geometric shape made up of 4 cells. The marked cell in the T-tetromino is known as the central cell.
Manka has drawn a rectangular grid with m rows and n columns, filling each cell with a number. The rows are numbered from 0 to m - 1, and the columns from 0 to n - 1. She has also designated some cells as special by, for example, coloring them red. Manka then challenges her friend Nika to place several T-tetrominoes on the grid under the following conditions:
The number of T-tetrominoes must equal the number of special cells.
Each T-tetromino's central cell must be positioned on a special cell.
No two T-tetrominoes may overlap.
All T-tetrominoes must fit entirely within the grid. Note that each T-tetromino can be oriented in 4 different ways.
If these conditions cannot be satisfied, Nika should respond with No. If they can be met, she should arrange the T-tetrominoes to maximize the sum of the numbers in the cells they cover. In this case, she should report the maximum sum of the covered T-tetromino cells to Manka. Write a program to assist Nika in solving this task.
Input
The first line contains two integers m and n — the height and width of the grid. The next m lines each contain n integers ranging from 0 to 1000. The j-th integer in the i-th line represents the number in the j-th cell of the i-th row. The following line contains the integer k [1,.....,m*n] — the number of special cells in the grid. Each of the next k lines contains two numbers r[i] and c[i], where r[i] [0,....,m-1] and c[i] [0,....,n-1] are the row and column indices of the i-th special cell, respectively. It is guaranteed that all special cell coordinates are unique.
Output
Output the maximum possible sum of the numbers covered by the T-tetromino cells, or No if it's impossible to place them.
Constraints
(1 ≤ mn ≤
10^6)
Explanation for the first example
