题目描述

乡村越野滑雪比赛在一个 $\red{m×}$$\red{n (1<=m,n<=500）}$的二维表格中进行，每个格子的海拔在 $\red{0 }$至 $\red{1000 }$之间。

滑雪者可以从一个格子滑到相邻格子，（可以从高处滑到低处，也可以从低处滑到高处），难度值 $\red{D }$是两者之间的海拔差的绝对值。相邻的格子是指有公共边的格子。

一条路径的难度值是指该路径上相邻两格子的难度值的最大值。

现在给出若干个关键格子，求所有这些关键格子相互可达的最小的难度值 $\red{D}$。

输入格式

第$\red{1}$行:整数$\red{M}$和$\red{N}$。

第$\red{2 . .1+M}$行:每条$\red{M}$线都包含$\red{N}$整数高程。

第$\red{2 + M . .1+2M}$行:每条$\red{M}$线包含的$\red{N}$值为$\red{0}$或$\red{1，}$其中$\red{1}$表示一个单元格是一个路径点。

输出格式

滑雪场地用$\red{3 ×}$ $\red{5}$的网格来描述。

左上、右上和右下单元格被指定为路径点。

样例

输入样例

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

提示

如果$\red{D = 21，}$则三个航路点可以互相到达。

如果$\red{D < 21，}$则从其他两个点无法到达右上角航路点。