Maximizing Land Development Profit

GDOI has acquired a rectangular piece of land divided into an \(N \times M\) grid. For each cell in row \(i\) and column \(j\), building a commercial area yields a profit of \(A_{i,j}\) and building an industrial area yields \(B_{i,j}\). In addition, if a cell \((i,j)\) has \(k\) neighbors (neighbors share a side, and \(k \le 4\)) that are developed in a different way from it, an extra profit of \(k \times C_{i,j}\) is earned for that cell.

Your task is to select a development scheme (i.e. choose for each cell to be either commercial or industrial) such that the total profit is maximized. The total profit is computed as follows for each cell \((i,j)\):

[ \text{Profit}(i,j) = \begin{cases} A_{i,j} + (#\text{of neighboring cells with industrial areas}) \times C_{i,j} &\text{if cell }(i,j) \text{ is commercial},\[6pt] B_{i,j} + (#\text{of neighboring cells with commercial areas}) \times C_{i,j} &\text{if cell }(i,j) \text{ is industrial}. \end{cases} ]

Output the maximum total profit achievable.

inputFormat

The input begins with two integers \(N\) and \(M\) representing the dimensions of the grid.

Then follow \(N\) lines, each containing \(M\) integers. These lines form the matrix \(A\), where the \(j\)-th integer of the \(i\)-th line is \(A_{i,j}\).

After that, there are \(N\) lines for the matrix \(B\) in the same format.

Finally, there are \(N\) lines for the matrix \(C\) in the same format.

All integers are separated by spaces.

outputFormat

Output a single integer: the maximum total profit achievable under an optimal assignment.

sample

1 1
5
8
1

8