시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

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

We will call this figure a T-tetromino; a tetromino is just a fancy word for a connected geometric figure composed of four cells. The cell marked with will × be called the center cell.

Manca draws a rectangular grid with m rows and n columns and writes a number into each cell. The rows of the table are numbered from 0 to m-1 and the columns are numbered from 0 to n-1. She also marks some cells as special, e.g., by painting them red. After that, she asks Nika, a friend of hers, to place T-tetrominoes on the grid in such a way that the following conditions are met:

  • The number of T-tetrominoes has to be the same as the number of special cells. For each T-tetromino, its center cell has to lie on some special cell.
  • No pair of T-tetrominoes may overlap.
  • All T-tetrominoes have to completely lie on the grid.

Note that there are four possible orientations of each T-tetromino (┬, ┴, ├, and ┤).

If the conditions cannot be satisfied, Nika should answer No; if they can, she has to find such a placement of T-tetrominoes that the sum of the numbers in the cells covered by the T-tetrominoes is maximum possible. In this case, she has to tell Manca the maximum sum.

Write a program to help Nika solve the riddle.

입력

Each line contains a sequence of integers separated by a single space.

The first line of the input contains the integers m and n. Each of the following m lines contains n integers from the interval [0, 1000]. The j-th integer in the i-th line represents the number written in the j-th cell of the i-th row of the grid. The next line contains an integer k ∈ {1, ..., mn}. This line is followed by k more lines, each of which consists of integers ri ∈ {0, ..., m-1} and ci ∈ {0, ..., n-1}, which represent the position (the row index and column index, respectively) of the i-th special cell. The list of special cells does not contain any duplicates.

출력

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

제한

  • 1 ≤ mn ≤ 106

예제 입력 1

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

예제 출력 1

67

To achieve the maximum sum, Nika may place the tetrominoes as follows:

  • ┤ on the cell (1, 1);
  • ├ on the cell (2, 2);
  • ┴ on the cell (3, 4).

예제 입력 2

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

예제 출력 2

No