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

Cho lưới ô vuông kích thước dòng và cột, các dòng được đánh số từ tới từ trên xuống dưới, các cột được đánh số từ đến từ trái sang phải. Ở mỗi ô có ghi một số nguyên . 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 ) 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 ;
• dòng sau, mỗi dòng chứa số nguyên mô tả một dòng của lưới.

Dữ liệu ra:

• Chứa số nguyên 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