Trong cuộc thi đường lên đỉnh Olympia do nhà trường tổ chức, bạn Vân đã giành được vòng nguyệt quế. Để khích lệ, cô giáo chủ nhiệm quyết định tặng bạn Vân những món quà ý nghĩa. Cô giáo chủ nhiệm có chuẩn bị rất nhiều món quà, mỗi mòn quà lại có giá trị nhất định. Cô ghi giá trị của tất cả các món quà của cô lên một bảng hình vuông kích thước , mỗi ô một số là giá trị của một món quà. Ô ở dòng cột được gọi là ô . Cô giáo cho bạn Vân được chọn một hình vuông kích thước , bạn Vân sẽ nhận được tất cả các món quà có giá trị tương ứng trên hình vuông đó. Em hãy giúp bạn Vân tính xem tổng giá trị tối đa của các món quà bạn Vân có thể nhận được là bao nhiêu nhé.
Dữ liệu vào:
Dòng đầu chứa hai số nguyên dương cách nhau bởi một dấu cách;
dòng tiếp theo, dòng thứ chứa số nguyên dương là giá trị của các món quà cô ghi trên dòng thứ .
Dữ liệu ra:
Một số nguyên duy nhất là tổng giá trị các phần quà lớn nhất mà bạn Vận có thể nhận được.
Ví dụ:
Dữ liệu vào:
4 3
1 9 1 1
9 9 9 9
1 9 9 9
1 9 9 14
Dữ liệu ra:
86
Giải thích:
Cách chọn hình vuông có đỉnh trái trên là ô , đỉnh phải dưới là ô , tổng giá trị là .
