Maximum Height Difference

You are given a grid of integers with dimensions N × M and an integer K. Starting from any cell, you are allowed to make up to K moves. In one move, you can travel from the current cell to one of its four adjacent cells (up, down, left, right), but you cannot visit the same cell twice in the same traversal.

Your task is to compute the maximum possible difference between the highest and lowest values encountered during such a traversal. Formally, if you denote by \(v_{min}\) the minimum value and by \(v_{max}\) the maximum value encountered along a path (including the starting cell), you need to maximize \(v_{max}-v_{min}\) over all starting cells and all valid traversals with at most \(K\) moves.

Note: Moves are only allowed between adjacent cells in the four cardinal directions, and each cell can only be visited once per traversal.

inputFormat

The input is read from stdin and has the following format:

N M K
grid[0][0] grid[0][1] ... grid[0][M-1]
grid[1][0] grid[1][1] ... grid[1][M-1]
...
grid[N-1][0] grid[N-1][1] ... grid[N-1][M-1]

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 moves allowed.
• The next N lines each contain M integers representing the grid values.

outputFormat

Output a single integer to stdout: the maximum height difference (i.e. the difference between the maximum and minimum grid values) that can be obtained by following a valid path starting from any cell with at most K moves.

## sample

3 3 3
1 2 3
4 5 6
7 8 9

8

</p>