P8232 [AGM 2022 Qualification Round] 2048 Garden

This is a game similar to 2048. You have a grid with $n$ rows and $m$ columns, and each cell contains a number $a_{i,j}$. In total, you can perform magic $K$ times. Before each operation, the system will change the $a$ value of the leftmost empty cell among those with the smallest row index to $1$. If no such empty cell exists, then this magic stops executing and the game ends. The operation is as follows: you may “move” all cells up/down/left/right. Moving in one direction is defined as: first, move all cells in that direction until they can no longer move; then, starting from the boundary on that direction, repeatedly merge two cells with the same value and generate a new cell whose value is the original value $+1$. The figure below shows one complete operation (including the system’s change before the operation):  Now you want to maximize, after $K$ magics (assuming that even if the game ends early, your score can still be counted), the maximum value among all cells. Please output this value.

There are multiple test cases. For each test case, the first line contains three integers $n,m,K$. Then follow $n$ lines, each containing $m$ integers $a_{i,j}$.

For each test case, output the answer.

#### Constraints For $100\%$ of the testdata, it is guaranteed that $1\leq n,m\leq 2500$, $1\leq \sum (n\times m)\leq 2500$, $1\leq K\times K \leq \min(n,m)$, $0\leq a_{i,j}\leq 10^6$. #### Notes Translated from [AGM 2022 Qualification Round D Rainy Garden](https://judge.agm-contest.com/public/problems/18/text)。 Translated by ChatGPT 5