Consider an *r* × *c* board,
where every cell has a positive value.
You are located at the top left cell,
and you must go to the bottom right cell,
never leaving the board.
Every step must be made down or to the right,
with one exception: you can make *j* chess knight jumps
(each, in any of the eight possible ways).
Every time you pass by a cell you accumulate its value.
Optimize the benefit.

**Input**

Input consists of several cases.
Every case begins with *r*, *c* and *j*,
followed by *r* rows with *c* natural numbers between 1 and 10^{5}.
Assume that both *r* and *c* are between 3 and 100,
and that *j* is between 0 and 100.

**Output**

For every case, print the maximum possible benefit.

Public test cases

**Input**

3 5 0 2 20 20 3 20 3 1 1 1 1 50 2 5 1 4 3 5 1 2 20 20 3 20 3 1 1 1 1 50 2 5 1 4

**Output**

70 130

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++