Bài tập chưa có test

Tiếp tục vượt qua thử thách thứ hai khá dễ dàng. Các bạn còn rất nhiều thời gian nên đã nghĩ đến kỳ thi học sinh giỏi quốc gia VOI. Tuy nhiên, trước khi đến VOI thì các bạn phải vượt qua thử thách tiếp theo của ban tổ chức như sau: Di chuyển trên mặt phẳng quá dễ dàng với các thí sinh. Vì vậy, lần này ban tổ chức cho các thí sinh di chuyển trên các cột cao. Ban tổ chức bố trí ~ m ~ x ~ n ~ cột trong một lưới ô vuông kích thước ~ m ~ x ~ n ~, mỗi cột tại một ô vuông, cột tại ô ~ [i,j] ~ (hàng ~ i ~, cột ~ j ~ ) có độ cao là ~ H[i,j] ~ Có một số cột được quy định là cột may mắn. Để chúc may mắn cho các thí sinh, các thí sinh sẽ được xuất phát tại một cột may mắn bất kỳ và để dành nhiều may mắn nhất thì từ cột xuất phát, thí sinh cần nhảy đến được tất cả các cột may mắn khác. Thí sinh đang ở cột tại ô ~ [x,y] ~ chỉ có thể nhảy đến các cột tại các ô chung cạnh với ô ~ [x,y] ~ và chênh lệch độ cao giữa hai cột không vượt quá ~ c ~. Thí sinh cần tìm giá trị ~ c ~ nhỏ nhất sao cho xuất phát tại một cột may mắn bất kỳ có thể nhảy đến tất cả các cột may mắn khác.

Dữ liệu vào

• Dòng đầu ghi hai số nguyên dương ~ m ~ và ~ n ~
• ~ m ~ dòng tiếp theo, dòng thứ ~ i ~ ghi ~n ~ số nguyên ~ H[i,j] ~ với ~ 1≤ j ≤ N ~
• ~ m ~ dòng tiếp theo, dòng thứ ~ i ~ ghi ~ n ~ số nguyên ~ L[i,j] ~ với ~ 1≤ j ≤ N ~ ( ~ L[i,j]=1 ~ cho biết cột tại ô ~ [i,j] ~ là cột may mắn, ~ L[i,j]=0 ~ thì cột tại ô ~ [i,j] ~ không phải là cột may mắn)

Kết quả

Ghi một số là giá trị ~ c ~ nhỏ nhất tìm được.

Ràng buộc

• ~ 1 ≤ M, N ≤ 5 ~ x ~10^2 ~
• ~ 0 ≤ H[i,j] ≤ 10^9~
• 50% số tests tương ứng với 50% số điểm có ~ m, n ≤ 10^2, H[i,j] ≤ 10^3 ~
• 50% số tests tương ứng với 50% số điểm có ~ m, n ≤ 5x10^2, H[i,j] ≤ 10^9 ~

Ví dụ:

Input 1

3 4
23 28 78 15
29 20 16 26
81 40 60 68
1 0 0 1
0 0 0 0
0 0 0 1 

Output 1

20