Land Enclosure Plan

Problem Source

BZOJ 2132

Problem Description

Recently the real-estate company GDOI (Group of Dumbbells Or Idiots) obtained a plot of land for development from NOI (Nuts Old Idiots). The land is a rectangular region that can be divided into $N \times M$ small cells. GDOI wants to divide these cells into a commercial district and an industrial district for development. Depending on the terrain, building a commercial district or an industrial district in each cell yields different economic value. More specifically, for the cell in row $i$, column $j$, building a commercial district yields profit $A_{i,j}$ and building an industrial district yields profit $B_{i,j}$. In addition, adjacent cells (two cells are adjacent if they share a common edge) of different types give extra profit: if cell $(i, j)$ has $k$ adjacent cells (obviously $k \leq 4$) of a type different from $(i, j)$, then this cell gains an extra profit of $k \times C_{i,j}$. Professor Tiger.S has surveyed the land, so the profit matrices $A, B, C$ are already known. Can you help GDOI find a plan that maximizes the total profit?

Input Format

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

Lines $2$ to $N+1$: each contains $M$ integers, the commercial-district profit matrix $A$.

Lines $N+2$ to $2N+1$: each contains $M$ integers, the industrial-district profit matrix $B$.

Lines $2N+2$ to $3N+1$: each contains $M$ integers, the adjacent-extra-profit matrix $C$.

It is guaranteed that $N, M \leq 100$, and $0 \leq A_{i,j}, B_{i,j}, C_{i,j} \leq 10^3$.

Output Format

Output a single line containing one integer: the maximum profit.

Sample Input

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

Sample Output

81

Constraints

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