Oski inherits a farm of size N × M blocks (row: 1..N, and column: 1..M) from his deceased uncle. The farm was in a good condition, however, it's lacking of an irrigation system.
Oski is convinced that this farm needs an irrigation system, thus, he decides to build one. The irrigation system Oski wants to build is a simple one. It consists of exactly two irrigation paths:
Each irrigation path has a width of exactly one single block.
Due to some circumtances, the irrigation paths should split the farm into exactly 4 nonempty smaller farms (4 quadrants). Note that the blocks which are used for irrigation path cannot be used for farming purpose.
Oski has hired a land inspector to value each block of his farm in term of its fertility score. Having this information, Oski wants to build the irrigation system such that the total fertility score of its farm is maximized. Consider the following example.
1 1 1 1 1 1 1 1 1 1 1 9 1 4 1 1 9 1 4 1 1 1 2 1 1 1 1 2 1 1 10 2 1 1 1 10 2 1 1 1 1 1 1 1 1 1 1 1 1 1
In this example, Oski has a farm of size 5 × 5 blocks. The maximum possible total fertility score he can obtained is 30, i.e. by building the irrigation path on 3^{rd} row and 4^{th} column. The farm is splitted into 4 quadrants, each quadrant's total fertility score is: 1+1+1+1+9+1 = 14, 1+1 = 2, 102+1+1+1+1 = 12, 1+1 = 2, with the total of 14+2+12+2= 30.
Oski is also interested on where he should build the irrigation paths to achieve the maximum total fertility score. Let (r, c) represents the two irrigation paths, i.e. on r^{th} row and on c^{th} column. (Not so) coincidentally, block (r, c) is also the meeting point of the two irrigation paths.
Due to aesthetic reason, if there are multiple irrigation systems which produce the same maximum total fertility score, output the one which (r, c) has a smaller Manhattan distance to (⌈N/2⌉, ⌈M/2⌉). This will cause (r, c) to be closer to the center of the farm.
Note that:
If there are still multiple of such irrigation systems, output the one with smaller r. Finally, if there are still multiple of such irrigation systems, output the one with smaller c.
Input begins with two integers: N M (3 ≤ N, M ≤ 2,000) denoting the farm size (row and column, respectively). The next N lines, each contains M integers F_{i,j} (100 ≤ F_{i,j} ≤ 100) denoting the potential score for block on the i^{th} row and j^{th} column, where i = 1..N and j = 1..M.
Output consists of two lines. The first line contains a single integer denoting the highest possible score for the irrigation system. The second line contains two integers (separated by a single space) r and c, denoting the location of the horizontal irrigation path and vertical irrigation path, respectively. See the problem statement if there are multiple of such irrigation systems.
input  Example #1 
5 5 1 1 1 1 1 1 9 1 4 1 1 1 2 1 1 10 2 1 1 1 1 1 1 1 1  
output  
30 3 4  
explanation  
This is the example given in the problem statement. 
input  Example #2 
6 5 1 1 1 1 1 1 1 1 1 1 1 1 9 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1  
output  
28 2 2  
explanation  
There are 6 irrigations systems which produce the maximum total fertility score (of 28):

End of Problem