You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

说明

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

迷阵由n*m个相同的小房间组成，每个房间与相邻四个房间之间有门可通行。而第1行的m个房间有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