Maximize Chessboard Path Sum

Given an (n \times m) chessboard (A), your task is to select three points ((x_1, y_1)), ((x_2, y_1)) and ((x_1, y_2)) such that the following value (V) is maximized:

[ V = \sum_{i=\min(x_1,x_2)}^{\max(x_1,x_2)} A_{i,y_1} + \sum_{j=\min(y_1,y_2)}^{\max(y_1,y_2)} A_{x_1,j} - A_{x_1,y_1} ]

Note that the point ((x_1,y_1)) is counted in both sums so it is subtracted once. You are given the chessboard values and must output the maximum possible (V).

inputFormat

The first line contains two integers (n) and (m) representing the number of rows and columns of the chessboard. Each of the following (n) lines contains (m) integers denoting the values of the chessboard (A).

Note: Indices are 1-based, but you may use 0-based indexing in your implementation.

outputFormat

Output a single integer, the maximum value of (V) computed by choosing valid points ((x_1,y_1)), ((x_2,y_1)), and ((x_1,y_2)).

sample

2 2
1 2
3 4

9