Sau khi có được năng lực Spiderman, Peter Griffin muốn thử sử dụng sức mạnh mới của mình. Thành phố mà cậu đang training có \({n \times m}\) tòa nhà, được sắp xếp theo hình bảng. Tòa ở vị trí \({(i, j)}\) có độ cao \(a_{ij}\). Spiderman của Peter Griffin có một năng lực mà các spiderman trước đó không hề có, đó là cậu có thể điều chỉnh được độ đàn hồi của tơ nhện mà mình phóng ra. Từ một tòa nhà cậu có thể đu sang một toàn nhà kề cạnh nếu như lực đàn hồi \(d\) mà cậu sử dụng lớn hơn hoặc bằng chênh lệch chiều cao giữa hai tòa nhà. Peter đã vạch ra một số tòa nhà để cậu xuất phát và luyện đu tơ, để tiết kiệm sức lực, cậu muốn dùng tơ với ít độ đàn hồi nhất có thể. Với mỗi tòa nhà xuất phát, bạn hãy xác định độ đàn hồi \(d\) bé nhất có thể để Peter có thể đu tới ít nhất \(k\) tòa nhà.

Dữ liệu vào

• Dòng đầu tiên gồm 3 số \({n, m, k}\) \({(n, m \leq 500; k \leq n \times m)}.\)
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(m\) số nguyên, số thứ \(m\) là độ cao của tòa nhà \((i, j)\).
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa \(m\) số nguyện \(0/1\), trong đó số thứ \(j\) là \(1\) cho biết ô \({(i, j)}\) là một tòa nhà xuất phát.

Dữ liệu ra

• Một dòng duy nhất là tổng số độ đàn hồi bé nhất có thể theo yêu cầu bài toán của những tòa nhà xuất phát.

Ví dụ