T571522 好吃的炸弹

AWaDa!AKTang!

烤乐滋来到了一个布满陷阱的森林！ 这片森林有 $N^2$ 座房屋，每个房屋的危险度为 $a_{i, j}$，形成一个 $N \times N$ 的矩阵。 烤乐滋有一个承受度 $H$，他从 $(1, 1)$ 开始，移动至与它上下左右相邻的房屋。 如果当前房屋的 $a_{i, j} \le H$，烤乐滋可以安全通过。否则，他只能使用炸弹将这座房屋炸毁。 烤乐滋制造了 $K$ 颗炸弹，烤乐滋想知道自己至少要多少承受度才能安全地抵达 $(N, N)$。

第一行 $2$ 个整数 $N, K$。 接下来 $N$ 行每行 $N$ 个整数 $a_{i, j}$。

一行，最小的 $H$。

对于 $100 \%$ 的数据，$1 \le N \le 10^3, 0 \le K \le N^2, 1 \le a_{i, j} \le 10^9$。