Maximum Sum

Interview

Time limit2sMemory limit1024 MB

Summary

Given an m by n grid of integers, find the axis-aligned rectangle with the largest sum along its border and print that sum plus the corner coordinates.

Level: Medium6 of 10
Topics: Prefix sum, Brute force, Implementation, Array
Solved: No attempts yet

Problem

Today the newspaper <> published an unusual mathematical puzzle. One page of the newspaper is completely filled with a rectangular table with $m$ rows and $n$ columns. Each cell of the table contains an integer.

To solve the puzzle, you must find a nondegenerate rectangle whose vertices lie at the centers of table cells and whose sides are parallel to the sides of the table, such that the sum of the numbers written in the cells on the border of the rectangle is as large as possible.

After spending several hours on the puzzle without success, Sasha decided to write a program that would solve it for him. But here too he failed. Now he has no choice but to ask you for help.

Write a program that, given a table, finds the required rectangle.

Input

The first line of the input file contains two integers $m$ and $n$ ( $2 \le m, n \le 300$ ). Then follows a description of the table: $m$ lines, each containing $n$ integers $a_{i,j}$ ( $-10^4 \le a_{i,j} \le 10^4$ ).

Output

On the first line of the output file, print the integer $s$ , the maximum sum of the numbers on the border of the required rectangle. On the second line, print four positive integers: $x_1, y_1, x_2, y_2$ , the coordinates of the top-left and bottom-right cells of the chosen rectangle, respectively. Here $x$ is the row number and $y$ is the column number; rows are numbered from top to bottom starting from one, and columns are numbered from left to right starting from one. If there are several optimal solutions, print any of them.

Examples2

Example 1
Input
```
2 3
1 1 1
1 1 1
```
Expected output
```
6
1 1 2 3
```

Example 2

Input

5 4
9 -2 -1 3
-10 -5 1 -4
1 -1 2 -2
3 0 0 -1
2 2 -1 2

Expected output

8
3 1 5 3