Collecting Maximum Coins

You are given a grid with (N) rows and (M) columns, where each cell contains a certain number of coins. You can start from any cell in the grid and make at most (K) moves. In each move, you can go one step up, down, left, or right, without revisiting a cell during the same journey. Your task is to determine the maximum number of coins that can be collected by choosing the optimal starting cell and path.

Note: When (K = 0), you can only collect the coins on the starting cell.

inputFormat

The input is read from standard input (stdin). The first line contains three space-separated integers (N), (M), and (K) (the number of rows, number of columns, and the maximum number of moves, respectively). This is followed by (N) lines, each containing (M) integers representing the coin values in each cell of the grid.

outputFormat

Output a single integer to standard output (stdout), which is the maximum number of coins that can be collected.## sample

3 3 2
1 2 3
0 1 4
2 0 5

12