Đường trượt tuyết băng đồng tại Thế vận hội Moolympic được mô tả bằng một lưới độ cao \(M \times N\) (\(1 \le M,N \le 500\)), trong đó mỗi độ cao nằm trong đoạn từ \(0\) đến \(1\,000\,000\,000\).

Một số ô trong lưới được chỉ định làm các điểm kiểm soát của đường trượt. Ban tổ chức Moolympic muốn gán độ khó \(D\) cho toàn bộ đường trượt sao cho một cô bò có thể đi từ bất kỳ điểm kiểm soát nào đến bất kỳ điểm kiểm soát nào khác bằng cách liên tục trượt từ một ô sang một ô kề có chênh lệch độ cao tuyệt đối không quá \(D\). Hai ô được coi là kề nhau nếu một ô nằm ngay phía bắc, nam, đông hoặc tây của ô kia. Độ khó của đường trượt là giá trị nhỏ nhất của \(D\) sao cho mọi điểm kiểm soát đều có thể đi đến lẫn nhau theo cách này.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(M\) và \(N\).
• \(M\) dòng tiếp theo, mỗi dòng chứa \(N\) số nguyên là độ cao của các ô.
• \(M\) dòng cuối, mỗi dòng chứa \(N\) giá trị bằng \(0\) hoặc \(1\); giá trị \(1\) cho biết ô tương ứng là một điểm kiểm soát.

Ràng buộc

• \(1 \le M,N \le 500\).
• Mỗi độ cao nằm trong đoạn từ \(0\) đến \(1\,000\,000\,000\).

Dữ liệu ra

In ra độ khó của đường trượt, tức giá trị nhỏ nhất của \(D\) sao cho mọi điểm kiểm soát vẫn có thể đi đến lẫn nhau.

Ví 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

Nguồn

USACO 2014 January Contest, Silver — Cross Country Skiing

Tác giả: William Hu và Brian Dean, 2014.