该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

信号走廊 (signalcorridor)

题目描述

一座地下通信站由 $N \times M$ 个节点组成。第 i 行第 j 列的节点记为 (i, j)，它当前的信号强度为 $A_{i,j}$。

维护机器人需要从左上角 (1, 1) 走到右下角 (N, M)。每一步可以向上、下、左、右相邻节点移动一格。机器人经过的所有节点都会参与一次传输测试，本次测试的得分定义为：路径上所有节点信号强度的最小值。

在机器人出发前，你最多可以修复 K 个节点。每修复一个节点，可以把它的信号强度改成 1 到 $10^9$ 之间的任意整数。

请计算经过最优修复和最优路线选择后，测试得分最大可能是多少。

输入格式

第一行三个整数 N M K。

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

输出格式

输出一行一个整数，表示最大可能得分。

样例 #1

样例输入 #1

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

样例输出 #1

6

样例 #2

样例输入 #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

样例输入 #3

2 3 6
2 3 3
5 7 8

样例输出 #3

1000000000

数据范围

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