Ant Pathfinding
On an $n \times m$ grid, each cell has a weight. Initially, an ant is at a vertex of one of the cells, facing North. We only know how the ant turns, but not how far it travels before each turn. The ant's turns follow a specific pattern: the sequence of turns is always of the form: Right, Right, Left, Left, Right, Right... Left, Left, Right, Right, Right. That is, two right turns and two left turns alternate, and the sequence ends with two right turns followed by one additional right turn. We also know that the ant does not rotate twice at the same location, the path does not visit the same point more than once (except for the starting point), it must return to the starting point to end its journey, and the ant only turns at the vertices of the grid cells.
Let $k$ be the number of left turns divided by 2. When $k=0$, a possible path for the ant is shown below:
Turn sequence: Right, Right, Right.
When $k=1$, a possible path for the ant is shown below:
Turn sequence: Right, Right, Left, Left, Right, Right, Right.
Given the grid dimensions, the weight of each cell, and the value of $k$ (where $k = \text{number of left turns} / 2$), find the maximum possible sum of weights of the cells enclosed by the path.
Input
The first line contains three integers $n, m, k$, as described above. The next $n$ lines contain an $n \times m$ integer matrix representing the grid.
Output
A single integer representing the maximum possible sum of weights of the cells enclosed by the ant's path.
Constraints
- $1 \le n \le 100$
- $1 \le m \le 100$
- $0 \le k \le 10$
- The absolute value of each element in the grid does not exceed $10000$.
- A valid path is guaranteed to exist.
- $10\%$ of the data: all cell weights are non-negative.
- Another $20\%$ of the data: $n=2$.
- Another $30\%$ of the data: $k=0$.
Examples
Input 1
2 5 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
Output 1
-8
Note
Except for the second and fourth cells of the first row, all other cells must be enclosed to be at least valid.