Cho một bảng số nguyên kích thước và một số nguyên không âm .
Một hình chữ nhật con của bảng được gọi là hình chữ nhật ổn định nếu hiệu tuyệt đối giữa phần tử lớn nhất và phần tử nhỏ nhất trong hình chữ nhật đó không vượt quá (tức là trong phạm vi hình chữ nhật đó).
Nhiệm vụ của bạn là chọn ra hai hình chữ nhật ổn định không giao nhau (không có ô chung) sao cho tổng diện tích (số lượng phần tử) của hai hình chữ nhật này là lớn nhất.
Dữ liệu:
Dòng đầu chứa ba số nguyên và .
dòng tiếp theo, mỗi dòng chứa số nguyên biểu diễn bảng số .
Kết quả:
Một số nguyên duy nhất là tổng diện tích lớn nhất của hai hình chữ nhật tìm được.
Dữ liệu:
3 4 1
1 2 10 10
2 1 10 10
5 5 5 5
Kết quả:
8
(Giải thích: Chọn hình chữ nhật ở góc trên trái (các số 1, 2) có diện tích 4 và hình chữ nhật ở dòng cuối (các số 5) có diện tích 4. Tổng là 8. Hoặc chọn hai hình vuông ở trên trái và trên phải).
Giới hạn:
Subtask #1: 30% số điểm có .
Subtask #2: 40% số điểm khác có .
Subtask #3: 30% số điểm còn lại không có ràng buộc bổ sung ().
