题目描述

有一个 $N * N$ 大小的迷宫。初始状态下，配送员位于迷宫的左上角，他希望前往迷宫的右下角。

配送员只能沿着上下左右四个方向移动，从每个格子移动到相邻格子所需要的时间是 $1$ 个单位，他必须用最多 $K$ 个（也可以少于 $K$ 个）单位时间到达右下角格子。

迷宫的每个格子都有辐射值，配送员必须穿着防护能力不低于相应辐射值的防护服，才能通过该格子。

他希望知道，防护服的防护能力最少要达到多少，他才能顺利完成任务。

注意：配送员需要通过迷宫的左上角和右下角，因此防护服的防护能力必须大于等于这两个格子的辐射值。

输入格式

前两行各包含一个正整数，分别对应 $N$ 和 $K$。
后 $N$ 行各包含 $N$ 个整数，以空格分隔，表示地图上每个位置的辐射值。

输出格式

一个整数，表示配送员穿着防护服的最低防护能力。

2
2
1 3
2 1

2

解释#1

配送员可以选择通过左下角（辐射值为 2）的路线，耗费 2 单位时间。

5
12
0 0 0 0 0 
9 9 3 9 0
0 0 0 0 0
0 9 5 9 9
0 0 0 0 0

3

解释#2

最优路线：往右 2 格，往下 2 格，往左 2 格，往下 2 格，往右 4 格，耗费 12 单位时间，经过格子的最大辐射值为 3。

另外，在地图不变的情况下，如果 $K = 16$，输出为 0；如果 $K = 8$，输出为 5。

数据范围

• $2 \le N \le 1000$
• $K \ge 2N-2$，以保证题目有解。
• 所有辐射值都是非负整数，绝对值不超过 $10^9$。
• 对于 50% 的数据，$a_i \le 100$（辐射值不超过 100）。