크로스 컨트리 스키 코스

겨울 올림픽에서의 크로스 컨트리 스키 코스는 M x N 격자의 고도로 표현됩니다. (1 <= M,N <= 500), 각 고도는 0 .. 1,000,000,000 범위입니다.

이 격자의 일부 셀은 코스의 경유지로 지정됩니다. 올림픽의 주최자들은 스키어가 셀에서 인접 셀로 스키를 여러 번 타며, 절대 고도 차이가 D 이하인 셀로 이동하여 어떤 경유지에서든 다른 경유지로 도달할 수 있도록 전체 코스에 난이도 등급 D를 부여하고자 합니다. 두 셀이 인접해 있다는 것은 한 셀이 다른 셀의 북쪽, 남쪽, 동쪽, 또는 서쪽에 직접 위치해 있다는 것입니다. 코스의 난이도 등급은 이러한 방식으로 모든 경유지가 상호 도달 가능한 D의 최소값입니다.

• 1번째 줄: 정수 M과 N.
• 2번째 줄부터 M+1번째 줄까지: 이 M개의 줄 각각에는 N개의 정수 고도가 있습니다.
• 2+M번째 줄부터 1+2M번째 까지: 이 M개의 줄 각각에는 0 또는 1인 N개의 값이 있으며, 여기서 1은 경유지인 셀을 나타냅니다.

• 1번째 줄: 코스의 난이도 등급 (경유지가 서로 도달 가능한 상태로 유지되는 D의 최소값).