Trượt Tuyết Việt Dã

Cho một lưới $M\times N$ ô vuông, mỗi ô có một giá trị độ cao nguyên. Một số ô được đánh dấu là điểm kiểm tra (waypoint).

Hai ô kề nhau (theo 4 hướng: bắc, nam, đông, tây) được coi là có thể di chuyển giữa nhau nếu chênh lệch độ cao tuyệt đối của chúng $\le D$.

Tìm giá trị $D$ nhỏ nhất sao cho tất cả các điểm kiểm tra đều liên thông với nhau (có thể đến được từ bất kỳ điểm kiểm tra nào đến bất kỳ điểm kiểm tra nào khác thông qua các ô trung gian).

Dữ liệu vào

• Dòng 1: Hai số nguyên $M$ và $N$ ($1\le M,N\le 500$).
• $M$ dòng tiếp theo: Mỗi dòng gồm $N$ số nguyên là độ cao của từng ô ($0\le h\le {10}^9$).
• $M$ dòng tiếp theo: Mỗi dòng gồm $N$ số nguyên $0$ hoặc $1$, trong đó $1$ chỉ điểm kiểm tra.

Dữ liệu ra

• Một số nguyên duy nhất: giá trị $D$ nhỏ nhất.

Ràng buộc

• $1\le M,N\le 500$
• $0\le h\le {10}^9$
• Luôn có ít nhất một điểm kiểm tra.

Ví dụ