G. CHOOSE2 - Chọn hình Ver 2

Bộ nhớ: 512 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản

Đề bài

Cho lưới ô vuông kích thước m dòng và n cột, các dòng được đánh số từ 1 tới m từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái sang phải. Ở mỗi ô (i, j) có ghi một số nguyên a_{ij}\ (2 ≤ m, n ≤ 500, |a_{ij}| ≤ 10^7) . Phải lựa chọn một hình chữ nhật có cạnh song song với cạnh của lưới (kích thước mỗi chiều >1 ) và tổng các số trong các ô thuộc biên là lớn nhất.

Dữ liệu vào:

  • Dòng đầu tiên chứa hai số nguyên m, n ;
  • m dòng sau, mỗi dòng chứa n số nguyên mô tả một dòng của lưới.

Dữ liệu ra:

  • Chứa số nguyên r là tổng lớn nhất tìm được.

Ví dụ:

Dữ liệu vào:
2 3
1 1 1
1 1 1
Dữ liệu ra:
6
Dữ liệu vào:
5 4
9 -2 -1 3
-10 -5 1 -4
1 -1 2 -2
3 0 0 -1
2 2 -1 2
Dữ liệu ra:
8