题目描述

这是一个类似 2048 的游戏，你有一个 $n$ 行 $m$ 列的方格，每个方格上有一个数 $a_{i,j}$。

你总共可以操作 $K$ 次魔法，每次操作之前，系统都会将行号最小的前提下最靠左的空格子的 $a$ 值变为 $1$，如果不存在这样的空格子，那么这次魔法被停止执行并且游戏结束。

操作如下：你可以将每个格子向上/下/左/右“移动”。向一个方向移动的定义是，先将所有格子向那个方向移动直到不能移动，然后从对应的方向边界处开始不断合并两个值相同的格子然后生成一个新的值为原来的值 $+1$ 的格子。如下图即为一次完整的操作（包括操作前系统的改动）：

现在你想最大化 $K$ 次魔法后（假设游戏中途结束你的分数依然可以结算）你的每个格子上的最大值，请你求出这个值。

输入格式

输入有若干组数据，每组数据第一行三个数 $n,m,K$。

接下来 $n$ 行每行 $m$ 个数 $a_{i,j}$。

输出格式

对于每组数据，输出答案。

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

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $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$。

说明

翻译自 AGM 2022 Qualification Round D Rainy Garden。