Description

冬季 Moolympics 的越野滑雪赛道由一个 $M \times N$ 的高程网格描述（$1 \leq M, N \leq 500$），每个高程在 $0$ 到 $1,000,000,000$ 之间。网格中的某些单元被指定为赛道的航点。Moolympics 的组织者希望为整个赛道分配一个难度等级 $D$，以便奶牛可以通过从一个单元滑到相邻单元（绝对高程差最多为 $D$）的方式，从任何一个航点到达另一个航点。如果一个单元的正北、正南、正东或正西方向上有另一个单元，则这两个单元是相邻的。赛道的难度等级是 $D$ 的最小值，使得所有航点都可以通过这种方式相互到达。

Input Format

• 第 1 行：整数 $M$ 和 $N$。

• 第 2 行到第 $1+M$ 行：每一行包含 $N$ 个整数高程。

• 第 $2+M$ 行到第 $1+2M$ 行：每一行包含 $N$ 个值，这些值要么是 $0$，要么是 $1$，其中 $1$ 表示该单元是一个航点。

Output Format

滑雪赛道由一个 3 x 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

Hint

如果 $D = 21$，三个航点可以相互到达。如果 $D < 21$，则右上角的航点无法从其他两个航点到达。

题面翻译由 ChatGPT-4o 提供。