题目描述

一队士兵来到了敌军城外准备进攻，敌人在城外布置了防御迷阵，进入城池必须先通过这个迷阵。 迷阵由n*m个相同的小房间组成，每个房间与相邻的四个房间之间有可通行的门。第1行的m个房间各有一扇向外打开的门，是迷阵的入口。除第1行和第n行的房间外，其余每个房间都安装了激光杀伤装置，会对进入的人造成一定伤害，第i行第j列房间的伤害值为a[i,j]（第1行和第n行的a值全部为0）。 士兵可以选择任意多的人从任意入口进入，最终必须到达第n行的任意房间。一个士兵受到的伤害值为其经过路径上所有房间伤害值的最大值，现在需要找到行进路线，使得这个伤害值最小，求出该最小伤害代价。

输入格式

第一行有两个整数n、m，表示迷阵的大小。 接下来n行，每行有m个整数，第i行第j列的数表示a[i,j]。 数据范围：n、m≤1000，a[i,j]≤1000。

输出格式

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

样例输入

4 2
0 0
3 5
2 4
0 0

样例输出

3