Moolympic Skiing

题目描述:

Moolympic Skiing将在一个M*N的网格中举行，每格的高度范围是[0,10⁹];有些点被作为waypoint，现在需要设定一个rating值D，保证每头牛都能从每个waypoint到其他的waypoint，如果rating值是D，则牛就可以从一格跳到相邻格满足这两格的高度差不超过D。一格的相邻格子是东，南，西，北的网格。输出最小的D，满足所有的waypoint都能相互到达。

输入格式:

第一行两个整数n和m

接下里n行，每行m个整数，表示每个网格的高度。

接下来n行，每行m个整数，0或1。1表示waypoint。

输出格式:

输出满足条件的最小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

提示:

30%的数据,n和m的范围[1,100]; 

100%的数据,n和m的范围[1,500]; 
如果D=21，这3个waypoint就能相互到达。如果D<21,右上角的点，就不能到达其他两个点。

时间限制: 1000ms
空间限制: 128MB

---