Sân golf được biểu diễn bởi một lưới kích thước ~m×n~ ~(1≤m,n≤500)~. Mỗi ô của lưới có độ cao trong khoảng 0 đến ~10^9~ so với mực nước biển.

Tại một vài ô trong lưới này là các vị trí có đặt lỗ, tức là nơi vận động viên sẽ đánh bóng rơi vào đó và bắt buộc sẽ đi đến đó để nhặt bóng.

Ban tổ chức của Olympics muốn đánh giá độ chênh lệch độ cao ~d~ của sân golf bằng cách làm như sau:

Cho một nhân viên bắt đầu di chuyển từ một vị trí đặt lỗ bất kỳ đến một trong bốn ô kề cạnh với ô đang đứng, có trị tuyệt đối chênh lệch độ cao không quá ~d~. Tại ô mới này, anh ta lại di chuyển tiếp sang một trong bốn ô kề cạnh có trị tuyệt đối chênh lệch độ cao không quá ~d~. Cứ thế tiếp tục cho đến khi có thể đến được tất cả các lỗ.

Yêu cầu: Hãy xác định độ chênh lệch độ cao ~d~ nhỏ nhất mà từ một lỗ bất kỳ có thể đến được tất cả các lỗ còn lại.

Dữ liệu vào:

• Dòng 1: chứa 2 số nguyên ~m,n~.
• ~m~ dòng tiếp theo: mỗi dòng chứa ~n~ số nguyên là độ cao của ô.
• ~m~ dòng tiếp theo: mỗi dòng chứa ~n~ giá trị là 0 hoặc 1, trong đó ô có giá trị 1 cho biết tại vị trí đó có lỗ, ngược lại thì tại đó không có lỗ.

Các số ghi trên cùng một dòng cách nhau bởi ít nhất một kí tự trắng.

Kết quả:

• Ghi số nguyên dương ~d~ cần tìm.

Ví dụ:

Input

3 5 
25 21 18 76 15
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 

Output

20