题目背景

题目传送门 U447586 海的魔法

由于你上一题 “STJX0001 赵老尸大战王之栋” 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$ 个整数，表示每个格子学生的初始警撅度。

输出格式

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

3 5
0 9 2 3 5
4 9 1 9 3
4 2 3 9 1

5

3 4
0 5 2 1
5 1000 7 1000
3 1000 1 9

9

说明/提示

【数据范围】

• 对于 $100\%$ 数据，$1 \le n,m \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$ 秒短的时间时，不存在一条合法的路径。

传送门

本题洛谷同步上传。U579657 王之栋的魔法