D. A Giraffe Travels and Munches
time limit per test
2 seconds
memory limit per test
256 mebibytes
input
standard input
output
standard output

Consider a rectangular field of size $$$m \times n$$$. In the upper left square with coordinates $$$(1, 1)$$$, the starting point, there is a giraffe. It wants to get to the lower right square with coordinates $$$(m, n)$$$: the destination. Each square of the field is characterized by an integer: the number of trees in it.

The giraffe can make two types of moves: down by $$$k$$$ squares and right by $$$1$$$ square; or right by $$$k$$$ squares and down by $$$1$$$ square. The giraffe wants to traverse the field from the starting square to the destination. At the end of each move, the giraffe eats the leaves on the trees at the square where it arrived. The giraffe does not eat anything at the starting square. On every even move, the giraffe feels hungry and eats $$$3t$$$ leaves, and on every odd move, it feels full and eats only $$$t$$$ leaves, where $$$t$$$ is the number of trees on the square. Moves are numbered starting from 1.

Determine the maximum number of leaves the giraffe can eat on its journey.

Input

The first line contains two integers separated by a space: $$$m$$$ and $$$n$$$ ($$$1 \le m, n \le 100$$$).

The second line contains an integer $$$k$$$ ($$$1 \le k \le \min (m, n)$$$).

Each of the next $$$m$$$ lines contains $$$n$$$ numbers; the $$$j$$$-th number in the $$$i$$$-th of these lines is the number of trees in the square $$$(i, j)$$$, and it is an integer in the range from $$$0$$$ to $$$100$$$, inclusive.

Output

Output a single integer: the maximum number of leaves the giraffe can eat on a path from the starting square to the destination. If there are no such paths, output $$$-1$$$.

Examples
Input
2 2
1
1 1
1 1
Output
1
Input
3 5
2
1 2 0 3 1
2 4 5 7 8
3 0 7 1 0
Output
5
Input
3 2
1
1 3
2 4
1 2
Output
-1