Maximum benefit path P32049

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⁵. 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.