Taco Redistribution

You are given a grid with R rows and C columns. Each cell in the grid contains a stack of boxes with a given height. You are allowed to move boxes between stacks. In one move, you can remove one box from a stack and add it to another stack. However, you cannot perform more than M moves in total.

Your goal is to minimize the difference between the highest stack and the lowest stack after performing at most M moves. Formally, if the final heights are \(h_1, h_2, \dots, h_{R\times C}\), you want to minimize \(\max_{i}(h_i)-\min_{i}(h_i)\).

Note: It is allowed to add boxes to a stack or remove boxes from a stack as long as the total number of moves does not exceed M. The boxes removed from one stack can be added to another. Moves are counted on a per-box basis.

This problem requires a careful strategy to determine whether a given difference \(d\) (where \(d = h_{max} - h_{min}\)) is achievable with the limited number of moves. A typical approach is to use binary search over the possible values of \(d\) and check the feasibility of each candidate difference.

inputFormat

The first line contains three integers R, C, and M separated by spaces.

This is followed by R lines, each containing C integers. The i-th line represents the heights of the box stacks in the i-th row of the grid.

You should read from standard input.

outputFormat

Output a single integer — the minimum possible difference between the highest and lowest stack after performing at most M moves.

The answer should be written to standard output.

## sample

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

2