Problem Description

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.

Input Format

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}$.

Output Format

For each test case, output the answer.

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

6
2

Hint

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。

Translated by ChatGPT 5