防御迷阵

题目描述

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

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

士兵可以选择任意多的人从任意入口进入，最终必须到达第 $n$ 行的任意房间。一个士兵受到的伤害值为其经过路径上所有房间伤害值的最大值，现在需要找到行进路线，使得这个伤害值最小，求出该最小伤害代价。

输入格式

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

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

输出格式

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

样例 #1

4 2
0 0
3 5
2 4
0 0

3

数据范围

对于 $100\%$ 的数据，$1 \leq n,m \leq 1000$，$0 \leq a_{i,j} \leq 1000$。