Maximum Points in Grid with One Special Move

You are given a grid of size \(n \times m\) where each cell contains an integer value. The grid is indexed from 1 to \(n\) in rows and 1 to \(m\) in columns. You need to start at the top‐left cell (1, 1) and move to the bottom‐right cell (\(n, m\)) by moving only to the right or down.

Additionally, there are \(k\) special cells given by their coordinates. At most one special move is allowed. When you land on a special cell, you may choose to perform a special operation that effectively lets you re‐start your remaining journey from that cell with an added bonus. Formally, if you reach a special cell at position \((r, c)\) (using 1-indexing) and your points accumulated up to that cell is \(D_{r,c}\), then you have the option to add \(D_{r,c}\) to the value of any subsequent cell along a normally computed path.

The standard dynamic programming recurrence for moving in the grid without a special move is:

[ \text{dp}[i][j] = \text{grid}[i][j] + \max\begin{cases} \text{dp}[i-1][j] & \text{if } i > 0\ \text{dp}[i][j-1] & \text{if } j > 0 \end{cases} ]

Your task is to compute the maximum points possible when starting from the top-left corner and reaching the bottom-right corner, while using at most one special move. If no special move is used, the answer is simply \(\text{dp}[n][m]\) computed by the recurrence above.

inputFormat

The input is read from standard input (stdin) and has the following format:

 n m k
 row1 (m space-separated integers)
 row2
 ...
 rown
 special_cell_1_row special_cell_1_col
 special_cell_2_row special_cell_2_col
 ...
 special_cell_k_row special_cell_k_col

If \(k=0\), then no special cell coordinates will be provided.

outputFormat

Print to standard output (stdout) a single integer representing the maximum points that can be accumulated from the top-left to the bottom-right cell using at most one special move.

## sample

3 3 0
1 2 3
4 5 6
7 8 9

29

</p>