题目描述

在冬季哞林匹克运动会上，越野滑雪赛道的规划是一个重要环节。赛事组织者需要确保所有赛道上的路标点之间都能互相到达。

越野滑雪赛道可以看作一个 $M \times N$ 的网格，每个单元格都有一个特定的海拔高度。相邻的单元格是指在北、南、东、西四个方向上直接相邻的单元格。

赛事组织者希望为整个赛道分配一个难度等级 $D$。一名滑雪者可以在两个相邻的单元格之间滑行，前提是它们之间的海拔高度差的绝对值不超过 $D$。

你的任务是确定最小的难度等级 $D$，使得所有被指定为路标点的单元格都能相互到达。

输入格式

第一行包含两个整数 $M$ 和 $N$，分别表示网格的行数和列数。

接下来 $M$ 行，每行包含 $N$ 个整数，表示网格中每个单元格的海拔高度 $E_{i,j}$。

接下来 $M$ 行，每行包含 $N$ 个整数，每个整数为 $0$ 或 $1$，其中 $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

21

数据规模与约定

样例说明 #1

当 $D = 21$ 时，所有三个路标点（左上、右上、右下）可以互相到达。 当 $D < 21$ 时，右上方的路标点无法从其他两个路标点到达。

说明/提示

对于所有测试数据： $1 \le M, N \le 500$ $0 \le E_{i,j} \le 10^9$ 至少有两个路标点。