一个 n×m 的迷阵由相同房间组成，相邻四个房间之间可以通行。第一行的房间是入口，第 n 行的每个房间都有一个必须打开的机关。除第一行和第 n 行外，进入第 i 行第 j 列房间会受到 p_{i,j} 点伤害。

可以安排任意多名士兵从任意入口进入，并要求到达第 n 行的每个房间。一个士兵的伤害值是其路径上房间伤害值的最大值，整个部队的伤害值是所有士兵伤害值的最大值。求完成任务时整个部队的最小伤害值。

输入格式

第一行两个整数 n,m。

接下来 n 行，每行 m 个整数 p_{i,j}。第一行和第 n 行的值均为 0。

输出格式

输出最小伤害值。

样例输入

4 2
0 0
3 5
2 4
0 0

样例输出

3

数据范围

50% 的数据 n,m ≤ 100；全部数据 n,m ≤ 1000，p_{i,j} ≤ 1000。

2 1
0
0

0

4 2
0 0
3 5
2 4
0 0

3

3 3
0 0 0
1 100 1
0 0 0

1