Maximizing Tile Value in a 2048‐Like Game

This problem is a variant of the popular 2048 game. You are given an n-by-m board with each cell containing an integer value \(a_{i,j}\) (a zero indicates an empty cell). You are allowed to perform at most \(K\) magic moves.

Before each move, the system performs an injection: it finds the empty cell with the smallest row index (and, if there are multiple, the leftmost among them) and sets its value to \(1\). If no empty cell exists, the magic move is cancelled and the game ends immediately. After the injection (if any), you choose a direction among up, down, left, or right and move every cell in that direction.

The moving process consists of two steps:

1. Sliding: All nonzero cells slide as far as possible in the chosen direction until no cell can move further (i.e. they are stopped either by the board boundary or by another tile).
2. Merging: Starting from the boundary in the moving direction, adjacent tiles with the same value are merged into a single tile with value increased by \(1\) (i.e. if two adjacent tiles both hold \(x\), they merge into a tile with \(x+1\)). Each tile can merge at most once per move, and merging is performed in one pass starting from the border.

Your task is to choose the move directions for the \(K\) magic moves (if the game does not end early) so as to maximize the maximum value among all cells after all moves are completed (even if the game terminates early due to lack of an empty cell for injection). Output that maximum value.

Note: All formulas should be interpreted in \(\LaTeX\) format.

inputFormat

The first line contains three integers \(n\), \(m\), and \(K\) representing the number of rows, columns, and magic moves respectively.

Then follow \(n\) lines, each containing \(m\) integers. Each integer represents \(a_{i,j}\), the value in the cell; a value of 0 indicates an empty cell.

outputFormat

Output a single integer, which is the maximum value present on the board after performing the moves optimally (or when the game ends prematurely).

sample

2 2 1
0 0
0 0

1