Nhiệt độ

Một công ty xây dựng các phòng chăm sóc vật nuôi được mô tả bởi một hình chữ nhật kích thước $m\times n$ chia thành lưới ô vuông đơn vị. Mỗi ô là một phòng có nhiệt độ là một số nguyên trong đoạn $[0,{10}^9]$. Theo quy định các con vật phải được chăm sóc ở ít nhất $T$ phòng trước khi đưa đi tiêu thụ. Khi di chuyển các con vật từ phòng này qua phòng khác nó phải chịu sốc nhiệt là độ lệch nhiệt độ giữa hai phòng.

Khả năng chịu sốc nhiệt của con vật là một số $D$ nhỏ nhất sao cho con vật có thể di chuyển tới ít nhất $T$ phòng (tính cả phòng ban đầu). Biết rằng con vật ở một phòng có thể di chuyển sang các phòng có chung cạnh nếu độ chênh lệch nhiệt độ không vượt quá $D$.

Yêu cầu: Hãy giúp công ty tính tổng khả năng chịu sốc nhiệt của con vật ở các phòng cần được kiểm tra.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên dương $m,n,T$ $(m,n\le 500;T\le m\times n)$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa $n$ số nguyên, số thứ $j$ là nhiệt độ của phòng $(i,j)$.
• $m$ dòng tiếp theo, dòng thứ $i$ chứa $n$ số nguyên thuộc $\{0,1\}$, trong đó số thứ $j$ là $1$ cho biết phòng $(i,j)$ là phòng có con vật cần được kiểm tra.

Dữ liệu ra

In ra một số nguyên duy nhất là tổng khả năng chịu sốc nhiệt của con vật ở các phòng cần được kiểm tra.

Ràng buộc

• $1\le m,n\le 500$, $1\le T\le m\times n$
• Nhiệt độ mỗi phòng là số nguyên trong đoạn $[0,{10}^9]$

Subtasks

• Subtask 1 ($25\%$ số điểm): $1\le m,n\le 10$.
• Subtask 2 ($25\%$ số điểm): $10<m,n\le 100$.
• Subtask 3 ($50\%$ số điểm): Không có giới hạn gì thêm.

Ví dụ