L. 防护设备

传统题

1000ms

256MiB

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

题目描述

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

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

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

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

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

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

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

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

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

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