Đường trượt tuyết băng đồng tại Moolympics mùa đông đượ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 điểm xuất phát của đường trượt. Ban tổ chức Moolympics muốn gán một mức độ khó cho mỗi điểm xuất phát. Mức độ khó của một điểm xuất phát \(P\) là giá trị nhỏ nhất có thể của \(D\) sao cho một cô bò bắt đầu tại \(P\) có thể đi đến tổng cộng ít nhất \(T\) ô trong lưới (\(1 \le T \le MN\)), với điều kiện cô chỉ có thể di chuyển từ một ô sang ô kề nếu chênh lệch tuyệt đối giữa độ cao của hai ô không vượt 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.

Hãy giúp ban tổ chức tính mức độ khó của từng điểm xuất phát.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên \(M\), \(N\) và \(T\).
• \(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 xuất phát.

Ràng buộc

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

Dữ liệu ra

In ra tổng mức độ khó của tất cả các điểm xuất phát. Lưu ý rằng tổng này có thể không biểu diễn được bằng số nguyên \(32\) bit, mặc dù từng mức độ khó riêng lẻ thì có thể.

Ví dụ

3 5 10
20 21 18 99 5
19 22 20 16 17
18 17 40 60 80
1 0 0 0 0
0 0 0 0 0
0 0 0 0 1

24

Nguồn

USACO 2014 January Contest, Gold — Ski Course Rating

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