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 \dots 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.

Input

• Dòng ~1~ 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.

Output

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.

Scoring

Sample Input 1

4 4 8
15 20 18 100
13 19 23 26
18 17 40 60
19 35 26 30
1 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1

Sample Output 1

21

Sample Input 2

4 4 8
15 20 18 100
13 19 23 26
18 17 40 60
19 35 26 30
1 1 0 0
0 0 0 0
0 0 0 0
0 0 0 1

Sample Output 2

25

Notes

Trong ví dụ thứ nhất, khả năng chịu nhiệt của con vật ở phòng ~(1,1)~ là ~5~ và ở phòng ~(4,4)~ là ~16~. Vậy tổng khả năng chịu sốc nhiệt của ~2~ con ở ~2~ phòng là: ~5+16=21~.

Trong ví dụ thứ hai, khả năng chịu nhiệt của con vật ở phòng ~(1,1)~ là ~5~, ở phòng ~(1,2)~ là ~4~ và phòng ~(4,4)~ là ~16~. Vậy tổng khả năng chịu sốc nhiệt của ~3~ con ở ~3~ phòng là: ~5+4+16=25~.