Description

With ambitions of colonial expansion, Pear and his interstellar fleet land on a plain of planet X. To evaluate the potential value of this land, Pear divides it into an $M \times N$ grid. Each cell is assigned an integer (possibly positive or negative) representing its value.

Pear’s task is simple: choose some cells to occupy, and separate them from the other land by building fences. For an $M \times N$ grid, there are a total of $(M+1) \times N + M \times (N+1)$ fence segments, that is, each cell has four fence segments on its top, bottom, left, and right; fence segments not on the boundary are shared by two adjacent cells. This is roughly shown in Figure 1.

In the figure, a blue segment is a fence shared by cells 1 and 2; a red segment is a fence shared by cells 3 and 4.

Each cell yields a profit that may be positive or negative, while the cost of building any fence segment is always positive.

You need to choose some cells, then choose some fence segments to enclose them, so that all chosen cells and all unchosen cells are strictly separated by fences. The chosen cells do not have to be connected, and they may contain “holes”, meaning that within a connected component there can be some cells that are not chosen. Note that if there is a “hole”, then by definition, the “hole” must also be separated from the connected component by fences.

Pear’s goal is clear: obtain the maximum profit with the minimum cost.

Input Format

The first line contains two positive integers $M, N$, representing the number of rows and columns.

The next $M$ lines each contain $N$ integers, forming a matrix $A$, where $A_{i,j}$ denotes the value of the cell in row $i$ and column $j$.

The next $M+1$ lines each contain $N$ integers, forming a matrix $B$, where $B_{i,j}$ denotes the cost to build the fence segment above the cell in row $i$ and column $j$.

In particular, $B_{M+1,j}$ denotes the cost to build the fence segment below the cell in row $M$ and column $j$.

The next $M$ lines each contain $N+1$ integers, forming a matrix $C$, where $C_{i,j}$ denotes the cost to build the fence segment to the left of the cell in row $i$ and column $j$.

In particular, $C_{i,N+1}$ denotes the cost to build the fence segment to the right of the cell in row $i$ and column $N$.

Output Format

One line containing a single positive integer, the maximum profit.

3 3
65 -6 -11
15 65 32
-8 5 66
4 1 6
7 3 11
23 21 22
5 25 22
26 1 1 13
16 3 3 4
6 3 1 2

123

6 6
72 2 -7 1 43 -12
74 74 -14 35 5 3
31 71 -12 70 38 66
40 -6 8 52 3 78
50 11 62 20 -6 61
76 55 67 28 -19 68
25 4 5 8 30 5
9 20 29 20 6 18
3 19 20 11 5 15
10 3 19 23 6 24
27 8 16 10 5 22
28 14 1 5 1 24
2 13 15 17 23 28
24 11 27 16 12 13 27
19 15 21 6 21 11 5
2 3 1 11 10 20 9
8 28 1 21 9 5 7
16 20 26 2 22 5 12
30 27 16 26 9 6 23

870

Hint

For $20\%$ of the testdata, $M, N \le 4$.

For $50\%$ of the testdata, $M, N \le 15$.

For $100\%$ of the testdata, $M, N \le 200$.

The absolute values of all entries in arrays $A, B, C$ (all input data involving cells and fences) do not exceed $1000$. According to the statement, entries of $A$ may be positive or negative, while entries of $B, C$ are all positive integers.

Time limit: 3 seconds, 256 MB. Lanqiao Cup 2014, the 5th National Finals.

Translated by ChatGPT 5