T - Covering#9047
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 cells. The marked cell in the T-tetromino is known as the central cell.
Manka has drawn a rectangular grid with rows and columns, filling each cell with a number. The rows are numbered from to m - 1, and the columns from 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 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.
The first line contains two integers and — the height and width of the grid (1 \leq m \cdot n \leq 10^6). The next lines each contain integers ranging from to . The -th integer in the -th line represents the number in the -th cell of the -th row. The following line contains the integer (1 \leq k \leq m \cdot n) — the number of special cells in the grid. Each of the next lines contains two numbers r_i and c_i, where r_i (0 \leq r_i \leq m-1) and c_i (0 \leq c_i \leq n-1) are the row and column indices of the -th special cell, respectively. It is guaranteed that all special cell coordinates are unique.
Output the maximum possible sum of the numbers covered by the T-tetromino cells, or No if it's impossible to place them.
Esempio 1
Esempio 2