Taco: Maximum Items Collection

You are given a warehouse represented as a grid with n rows and m columns. Each cell of the grid contains a non-negative integer indicating the number of items available at that cell.

You need to determine the maximum number of items a supervisor can collect. The supervisor may start from any cell on the grid and move to adjacent cells (up, down, left, right). However, the supervisor can take at most k steps. Each cell's items are only collected the first time the supervisor visits that cell. The goal is to collect as many items as possible without exceeding the allowed number of steps.

Note: A step consists of moving from the current cell to an adjacent cell. Even if k is 0, the supervisor can still collect the items at the starting cell.

The problem can be formally formulated as finding the maximum sum along any simple path (no revisits) on the grid, where the length of the path (in steps) does not exceed k.

In mathematical terms, if we denote the grid by \(G\) where \(G_{i,j}\) is the number of items at cell \((i,j)\), and \(P\) is a path starting at some cell \((i,j)\) with at most \(k\) moves, then the objective is to maximize \[ \text{score}(P)=\sum_{(i,j)\in P}G_{i,j} \] subject to \(|P|-1 \le k\).

inputFormat

The input is given via stdin and has the following format:

n m k
row1
row2
... 
rown

Where:

• n is the number of rows in the grid.
• m is the number of columns in the grid.
• k is the maximum number of steps allowed.
• Each of the next n lines contains m space-separated non-negative integers representing a row of the grid.

outputFormat

Output (via stdout) a single integer representing the maximum number of items that can be collected under the given constraints.

## sample

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

4