Giá trị chiếc quạt mo
Phú ông có một mảnh đất hình chữ nhật được chia thành lưới ô vuông gồm M hàng và N cột. Các hàng của lưới được đánh số từ trên xuống dưới bắt đầu từ 1, còn các cột – đánh số từ trái sang phải, bắt đầu từ 1. Ô nằm giao của hàng i và cột j là ô đất i,j (i=1..M,j=1..N) có độ cao là hij. Phú ông đã đưa ra đề nghị đổi chiếc quạt mo lấy đất như sau:
- Bờm được quyền chọn 2 mảnh đất con (một mảnh để làm nhà, một mảnh để trồng rau), hai mảnh đều có dạng hình chữ nhật và chứa nguyên các ô.
- Mỗi mảnh đất có độ chênh lệch không quá K, nghĩa là hiệu độ cao của ô có độ cao nhất với ô có độ cao thấp nhất không vượt quá K.
- Hai mảnh đất được chọn không không giao nhau nhưng có thể tiếp xúc nhau.
- Hãy giúp Bờm chọn được hai mảnh đất thỏa mãn điều kiện của phú ông và có tổng diện tích là lớn nhất.
Dữ liệu
- Dòng đầu là 3 số M,N và K (M,N≤300)
- M dòng sau, mỗi dòng gồm N số nguyên hij mô tả mảnh đất (K,|hij|<109)
Kết quả
Chứa một số là tổng diện tích lớn nhất tìm được.
Ví dụ
Dữ liệu 3 4 0 1 2 3 1 1 9 9 1 2 2 2 2 Kết quả 6
