Giải bài trực tuyến

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à h_ij. 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 h_ij mô tả mảnh đất (K,|h_ij|<10⁹)

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

Lưu ý: Có 50% số test với m,n≤50.