暂无测试数据。

小明陷进了一个迷宫！这个迷宫是网格图形状的。小明一开始在 $(1,1)$ 位置，出口在 $(n,m)$ 。而且这个迷宫里有很多怪兽，若第 $a$ 行第 $b$ 列有一个怪兽，且此时小明处于第 $c$ 行 $d$ 列，此时这个怪兽对它的威胁程度为 $|a-c|+|b-d|$。

小明想找到一条路径，使得它能从 $(1,1)$ 到达 $(n,m)$，且在途中对它威胁程度最小的怪兽的威胁程度尽可能大。

当然若起点或者终点处有怪兽时，无论路径长什么样，威胁程度最小的怪兽始终 $=0$。

输入格式

第一行两个数 $n,m$。

接下来 $n$ 行，每行 $m$ 个数，如果该数为 $0$，则表示该位置没有怪兽，否则存在怪兽。数据保证至少存在一个怪兽。

输出格式

一个数表示答案

数据范围

对于 $20\%$ 的数据 $n=1$

对于 $40\%$ 的数据 $n\leq2$

对于 $60\%$ 的数据 $n,m \leq 10$

对于 $80\%$ 的数据 $n,m\leq100$

对于 $90\%$ 的数据 $n,m\leq1000$

对于另外 $10\%$ 的数据 $n,m \leq 1000$ 且怪兽数量 $\leq 100$ 。

3 4
0 1 1 0
0 0 0 0
1 1 1 0

1