P6463 [ChuanZhi Cup #2 Finals] Building an Island.

"Animal Crossing: New Horizons" is a game with a very high degree of freedom. You can build houses, plant flowers and trees on your own deserted island, and you can also fish for sea bass.  If a square land of size $(2k-1)\times(2k-1)$ satisfies that the height of the outermost ring is 1, the height of the second ring is 2, and so on, then it is a pyramid of height $k$. The figure below shows examples of pyramids with height from 1 to 4:  Xiao A's island is a rectangle of size $n\times m$, and the height at each position is known. He wants to build a huge pyramid. He has at most $k$ chances to modify the terrain. Each time, he can choose a coordinate and increase the height at that point by 1, but he cannot decrease the height. What is the maximum possible height of the pyramid he can complete?

Each test point consists of multiple test cases. The first line contains an integer $T$, which is the number of test cases. For each test case, the first line contains three integers $n,m,k$, representing the island size and the upper limit on the number of operations. Then follows an $n$-row $m$-column matrix representing the initial heights, with spaces between numbers.

Output $T$ lines. For each line, output one integer, representing the maximum height of the pyramid that can be completed for that test case.

For all testdata, $1\le T \le 5$, $1 \le n,m \le 350$, $1\le k \le 10^8$, and the initial heights are non-negative integers from 0 to 50. # Constraints Translated by ChatGPT 5