本题需要文件读写

文件 IO 为：输入文件 route.in，输出文件 route.out。请使用上述文件名读入和输出。

问题描述

有一个 $N$ 行 $M$ 列的设备区域，第 $i$ 行第 $j$ 列的设备稳定度为 $A_{i,j}$。机器人从左上角 $(1,1)$ 到右下角 $(N,M)$，每一步只能移动到上、下、左、右相邻位置。路线质量为所有经过位置（包括起点和终点）的稳定度最小值。

出发前最多可以升级 $K$ 个位置，将每个升级位置的稳定度调整为 $1$ 到 $10^9$ 之间的任意整数。请计算经过最优升级和路线选择后，能得到的最大路线质量。

输入格式

从文件 route.in 中读入数据。

第一行输入三个整数 $N,M,K$。

接下来 $N$ 行，每行输入 $M$ 个整数，第 $i$ 行第 $j$ 个整数为 $A_{i,j}$。

输出格式

输出到文件 route.out 中。

输出一行一个整数，表示最大可能的路线质量。

样例输入 1

3 3 2
1 2 4
3 5 7
6 8 9

样例输出 1

6

样例输入 2

5 5 0
1 7 7 7 7
1 7 1 1 1
1 7 1 7 1
1 7 1 7 1
1 1 1 7 1

样例输出 2

1

样例输入 3

2 3 6
2 3 3
5 7 8

样例输出 3

1000000000

评测数据规模

• $2\le N,M\le300$；
• $0\le K\le N\times M$；
• $1\le A_{i,j}\le10^9$；
• 输入均为整数。