Trung tâm thương mại
Công ty E-Holding đang nghiên cứu quy hoạch của một khu đô thị. Biết rằng, phần đất của khu đô thị dành cho thương mại là một hình chữ nhật được chia thành $M$ hàng, $N$ cột. Lô đất ở ô có hàng thứ $i$ và cột thứ $j$ có giá trị $a_{i,j}$.
Công ty đang muốn tìm hai vị trí để xây hai tòa trung tâm thương mại. Mỗi tòa là một hình chữ nhật. Công ty muốn tổng giá trị của các lô đất thuộc hai tòa là lớn nhất.
Lưu ý: Hai tòa nhà không giao nhau. Hai tòa nhà được tính là giao nhau khi có ít nhất một lô đất thuộc hai tòa nhà.
Dữ liệu
- Dòng đầu tiên chứa hai số nguyên $N, M \ (0<N,M\le10^3)$;
- $N$ dòng tiếp theo, mỗi dòng chứa $M$ số nguyên $a_{i,j} \ (|a_{i,j}| \le 10^9)$.
Kết quả
- Tổng giá trị lớn nhất đó.
Ví dụ
Ví dụ 1
input
4 4
1 2 -2 1
2 3 -5 2
3 1 -7 3
1 2 -10 3
output
24
Comments