U579657 王之栋的魔法

题目传送门 [U447586 海的魔法](https://www.luogu.com.cn/problem/U447586) 由于你上一题 “[U578817 赵老尸大战王之栋](https://www.luogu.com.cn/problem/U578817)” WA过多，王某栋没能成功保卫他的 NOI 金牌，金牌被赵老师偷到了讲台 $(n,m)$ 上，教室也被赵老师夺舍。王之栋不想失去自己的金牌，于是决定潜入教室，偷回自己的金牌。

王某栋回到了 $n$ 行 $m$ 列的教室偷金牌，他位置在后门 $(1,1)$，金牌的位置在讲台 $(n,m)$ 上。 由于赵老师在巡视，每个格子上坐的学生都有一个警觉值 $h_i$，$(1,1)$ 位置学生在修自己的 OJ 警觉值为 $0$ 。王某栋只能偷偷潜入教室到讲台而不被发现，这要求网格图上存在一条从 $(1,1)$ 到 $(n,m)$ 的路径，使得路径上的每个学生的警觉值都 $\le 0$ 并且除了路径上第一个格子外，其它的格子都要和前一个格子上下相邻或者左右相邻。 显然，在很多情况下王某栋无法夺回金牌，但好在王某栋有一位海精灵同学，他可以顺着网线吟唱催眠魔法让教室里的所有学生每秒减少 $1$ 警觉值。王某栋想知道最快他得吟唱多少秒才能出现一条后门从 $(1,1)$ 通往讲台 $(n,m)$ 的路径。

第一行两个整数 $n,m$ ，表示该网格教室的长和宽。 接下来 $n$ 行，每行 $m$ 个整数，表示每个格子学生的初始警觉度。

输出一个整数，表示答案。

**【数据范围】** - 对于 $100\%$ 数据，$1 \le n,m \le 500$，$0 \le h_i \le 10^9$。 | 测试点编号 | $n$ | | ----------- | -------------------------------------- | | $1 \sim 4$ | $n = 1$,$0 \le h_i \le 10^9$ | | $5 \sim 10$ | $1 \le n \le 500$,$0 \le h_i \le 100$ | | $11 \sim 20$ | $1 \le n \le 500$,$0 \le h_i \le 10^9$ | **【样例 $1$ 解释】** 吟唱 $5$ 秒后，每个格子学生的警觉度变为： ``` -5 4 -3 -2 0 -1 4 -4 4 -2 -1 -3 -2 4 -4 ``` 出现了一条路径：$(1,1),(2,1),(3,1),(3,2),(3,3),(2,3),(1,3),(1,4),(1,5),(2,5),(3,5)$，路径上所有学生的警觉度都 $\le0$ 并且这些格子都是前后或者左右相邻。可以证明吟唱比 $5$ 秒短的时间时，不存在一条合法的路径。