A70717 | 防御迷阵

一队士兵来到了敌军城外，准备进攻敌城。敌人在城外布置一个防御迷阵，要进入城池首先必须通过城池外的防御迷阵。

迷阵由 n \times m 个相同的小房间组成，每个房间与相邻四个房间之间有门可通行。而第 1 行的 m 个房间有 m 扇向外打开的门，是迷阵的入口。除了第 1 行和第 n 行的房间外，每个房间都安装了激光杀伤装置，将会对进入房间的人造成一定的伤害。第 i 行第 j 列造成的伤害值为a_ij。 （第 1 行和第 n 行的 a_ij 值全部为0）。

现在士兵打算以最小伤害代价通过迷阵，显然，他们可以选择任意多的人从任意的门进入，但必须到达第 n 行的房间。一个士兵受到的伤害值为他在经过的路径上所有房间的伤害值中的最大值。现在，士兵们掌握了迷阵的情况，他们需要提前知道怎么安排士兵的行进路线可以使得伤害值最小。

第一行有两个整数 n,m 表示迷阵的大小。

接下来 n 行，每行 m 个数，第 i 行第 j 列的数表示 a_{ij} 。

数据范围：2≤n,m≤1000，1≤a_ij≤1000。

输出一个数，表示最小伤害代价。