Maximizing Classroom Joy

The problem is set in a classroom where the seating arrangement is given by an \(n \times m\) grid. Each cell represents a student. After a semester, every student becomes best friends with his/her neighbors (i.e. up, down, left, right). Each student obtains a certain personal joy from choosing one of two subjects: liberal arts or science. In addition, if a pair of best friends (neighbors) both choose the same subject then they obtain an extra bonus joy.

You are given two matrices and a bonus value:

• An \(n \times m\) matrix \(A\), where \(A_{i,j}\) is the joy for the student at row \(i\) and column \(j\) if they choose liberal arts.
• An \(n \times m\) matrix \(B\), where \(B_{i,j}\) is the joy if that student chooses science.
• A bonus integer \(d\) which is added for each pair of adjacent students (neighbors up, down, left, right) if they choose the same subject.

The goal is to determine an assignment of subjects to all students such that the total joy is maximized. The total joy is computed as follows:

[ \text{Total Joy} = \sum_{(i,j)} \text{joy}(i,j) + d \times \text{(number of adjacent pairs with same subject)} ]

Note that if a student has no adjacent friend in a certain direction (e.g. at the border), that direction is simply ignored. You can assume that \(n\) and \(m\) are small (e.g. \(n, m \le 4\)) so that an exhaustive search is computationally feasible.

inputFormat

The first line contains three integers \(n\), \(m\) and \(d\) -- the number of rows, columns and the bonus joy for each pair of adjacent friends who choose the same subject.

The next \(n\) lines each contain \(m\) integers. The \(i\)th line represents the row \(i\) of matrix \(A\) (joy values for liberal arts).

The next \(n\) lines each contain \(m\) integers. The \(i\)th line among these represents the row \(i\) of matrix \(B\) (joy values for science).

outputFormat

Output a single integer - the maximum total joy that can be achieved.

sample

1 1 5
3
4

4