Đề bài:

Cho một ma trận có kích thước ~m~ hàng và ~n~ cột chứa các số nguyên. Hãy tìm hình chữ nhật trong ma trận sao cho tổng các phần tử bên trong hình chữ nhật đó là lớn nhất.

Dữ liệu đầu vào:

• Dòng đầu tiên chứa hai số nguyên ~m, n~ ~(1 \leq m, n \leq 100)~.
• ~m~ dòng tiếp theo, mỗi dòng gồm ~n~ số nguyên (mỗi số có giá trị tuyệt đối không vượt quá ~10^9~).

Kết quả đầu ra:

• Dòng đầu tiên in ra tổng ~S~ lớn nhất của hình chữ nhật.
• Dòng thứ hai in ra 4 số nguyên tương ứng là:
  • Hàng, cột của đỉnh góc trên-trái.
  • Hàng, cột của đỉnh góc dưới-phải.

Ví dụ:

Input:

3 4
0 1 -2 0
1 -4 3 1
0 3 -1 4

Output:

7
2 3 2 4

Trong ví dụ trên, hình chữ nhật lớn nhất có tổng là ~7~, nằm từ hàng ~2~, cột ~3~ đến hàng ~2~, cột ~4~.