Description

On an $n \times m$ board, each cell has a weight. Initially, there is an ant facing north at the vertex of some cell. We only know how its route turns, but we do not know how far it walks between consecutive turns.

The ant’s turning sequence has a specific pattern: right, right, left, left, right, right, …, left, left, right, right, right. That is, pairs of right turns and pairs of left turns appear alternately; after the final pair of right turns (the last two are necessarily right turns), one additional right turn is appended. We also know that the ant will not rotate twice consecutively at the same position, the ant’s path will not pass through the same point more than once except for the starting point, it will finally return to the starting point and end its journey, and the ant only turns at grid vertices.

Given the board size, each cell’s weight, and the value of the number of left turns divided by $2$, find the maximum possible sum of weights of the closed shape enclosed by the ant’s path.

Input Format

The first line contains three integers $n, m, k$, as described above.

Then follow an $n$-row, $m$-column integer matrix representing the board.

Output Format

Output a single integer: the maximum possible total weight of the region enclosed by the ant’s path.

2 5 2
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1

-8

Hint

Sample Explanation: At minimum, both the second cell and the fourth cell in the first row must be enclosed for the path to be valid.

Constraints:

• $10\%$ of the testdata have all cell weights nonnegative.
• Another $20\%$ of the testdata have $n=2$.
• Another $30\%$ of the testdata have $k=0$.
• For $100\%$ of the testdata, $1 \le n\le 100$, $1 \le m \le 100$, $0 \le k \le 10$, a valid path is guaranteed to exist, the testdata have gradient, and the absolute value of each cell’s weight does not exceed $10000$.

Translated by ChatGPT 5