N. 滑雪比赛

传统题

1000ms

256MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

“哞林匹克”运动会中的一大亮点就是滑雪比赛。滑雪比赛的场地是一个 $n \times m$ 的矩阵（ $1 \le n,m \le 500$ ），每一个点有对应的海拔（海拔均在 $1$ 到 $10^9$ 的范围内）。

主办方指定了若干个点作为路标。同时，主办方还要规定一个比赛系数 $d$ ，这个系数规定选手不能在海拔高度差大于 $d$ 的两个点之间活动。在规则允许的范围内，选手可以向东南西北任意一个点活动，选手的任务是在尽量短的时间内到达所有的路标打卡。

为了确保每一个选手的安全，主办方想将系数 $d$ 设置得越小越好，然而这个系数要确保每一个路标是相互联通的（否则比赛就失去了意义）。

第一行输入两个整数 $n$ 和 $m$ ，表示比赛场地的大小；

接下来输入两个 $n \times m$ 的矩阵，第一个表示每一个点的海拔高度，第二个矩阵表示路标的设置情况，其中数字 $1$ 表示该点为路标，数字 $0$ 表示不是路标。

输出 $d$ 。

3 5
20 21 18 99 5
19 22 20 16 26
18 17 40 60 80
1 0 0 0 1
0 0 0 0 0
0 0 0 0 1