Description

Recently, the real estate developer GDOI (Group of Dumbbells Or Idiots) obtained a piece of land for development from NOI (Nuts Old Idiots). This land is a rectangular area that can be divided into $N \times M$ small cells. GDOI requires dividing these cells into a commercial zone and an industrial zone for development. Due to different terrain conditions, building a commercial zone or an industrial zone on each cell will yield different economic values. More specifically, for the cell in the $i$-th row and $j$-th column, building a commercial zone yields revenue $A_{i,j}$, and building an industrial zone yields revenue $B_{i,j}$. In addition, adjacent cells can bring extra revenue: if cell $(i,j)$ has $k$ neighboring cells (adjacency means two cells share a common side) whose type is different from that of $(i,j)$, then this cell gains an additional revenue of $k \times C_{i,j}$. After Professor Tiger.S’s survey, the revenue matrices $A$, $B$, and $C$ are known. Can you help GDOI find a plan that maximizes the total revenue?

Input Format

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

Lines $2$ to $N+1$: each line contains $M$ integers, representing the commercial revenue matrix $A$.

Lines $N+2$ to $2N+1$: each line contains $M$ integers, representing the industrial revenue matrix $B$.

Lines $2N+2$ to $3N+1$: each line contains $M$ integers, representing the extra revenue matrix $C$ for adjacent cells.

Output Format

Output a single line containing one integer, the maximum total revenue.

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

81

Hint

$1 \leq N, M \leq 10$, $0 \leq A_{i,j}, B_{i,j}, C_{i,j} \leq 10^3$.

Translated by ChatGPT 5