크로스컨트리 스키

겨울 무림픽(Moolympics)의 크로스컨트리 스키 코스는 높이가 적힌 $M \times N$ 격자로 주어진다 ($1 \le M, N \le 500$). 각 칸의 높이는 $0$ 이상 $10^9$ 이하의 정수다.

격자의 일부 칸은 코스의 경유지로 지정되어 있다. 대회 운영진은 코스 전체에 난이도 $D$를 매기려고 한다. 소는 높이 차이의 절댓값이 $D$ 이하인 인접한 칸으로 옮겨 가는 이동을 반복해서, 어느 경유지에서 다른 어느 경유지로도 갈 수 있어야 한다. 두 칸은 한쪽이 다른 쪽의 바로 북쪽, 남쪽, 동쪽, 서쪽에 있을 때 인접하다. 코스의 난이도는 이 조건을 만족하는 $D$ 중 가장 작은 값이다.

경유지가 두 개 미만이면 난이도는 $0$이다.

• 첫째 줄에 정수 $M$과 $N$이 주어진다.
• 다음 $M$개 줄에는 각각 $N$개의 높이가 주어진다.
• 이어지는 $M$개 줄에는 각각 $N$개의 값이 주어진다. 각 값은 $0$ 또는 $1$이고, $1$은 그 칸이 경유지라는 뜻이다.

• 첫째 줄에 코스의 난이도를 출력한다. 모든 경유지가 서로 오갈 수 있게 하는 $D$의 최솟값이다.

첫 번째 예제의 스키 코스는 $3 \times 5$ 격자다. 왼쪽 위, 오른쪽 위, 오른쪽 아래 칸이 경유지다.

$D = 21$이면 세 경유지는 서로 오갈 수 있다. $D$가 $21$보다 작으면 오른쪽 위 경유지에는 나머지 두 곳에서 닿을 수 없다.