题目内容

有一个$N×N$大小的迷宫。初始状态下，配送员位于迷宫的左上角，他希望前往迷宫的右下角。配送员只能沿着上下左右四个方向移动，从每个格子移动到相邻格子所需要的时间是$1$个单位，他必须用最多$K$个(也可以少于$K$个)单位时间到达右下角格子。迷宫的每个格子都有辐射值，配送员必须穿着防护能力不低于相应辐射值的防护服，才能通过该格子。他希望知道，防护服的防护能力最少要达到多少，他才能顺利完成任务。注意:配送员需要通过迷宫的左上角和右下角，因此防护服的防护能力必须大于等于这两个格子的辐射值。

输入描述

前两行各包含一个正整数，分别对应$N$和$K$。 后$N$行各包含$N$整数，以空格分隔，表示地图上每个位置的辐射值。 $2≤N≤100。K≥2N-2$，以保证题目有解。所有辐射值 都是非负整数，绝对值不超过 $10^4$。

输出描述

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

样例1

输入

2
2
1 3
2 1

输出

2

说明

配送员可以选择通过左下角(辐射值为2)的路线，耗费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$格，往右$4$格，耗费$12$单位时间，经过格子的最大辐射值为$3$。 另外，在地图不变的情况下，如果$K=16$，输出为$0$；如果K=$8$，输出为$5$。