27285번 - L-Board 서브태스크다국어

문제

Lord Pooty has a $n$ by $m$ board of integers $A$ and would like to draw an L. However, he would like to maximise the sum of integers on the tiles covered by L. The L can be rotated in all 4 possible orientations such that the sides are parallel to the board. Each side of the L may not necessarily be drawn (a straight line is possible). Some examples of valid Ls are shown below:

Formally, you want to choose 3ドル$ points, $(x_1, y_1),ドル $(x_2, y_1)$ and $(x_1, y_2)$ (which may not necessarily be distinct) on the board $A$ such that

$$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} $$

is maximised.

입력

Your program must read from standard input.

The input starts with a line with two integers $n$ and $m$ where $n$ and $m$ are height and width of the board. This is followed by $n$ lines of $m$ integers, representing the board.

출력

Your program must print to standard output.

The output should contain a single integer on a single line, the maximum $V$ possible.

제한

• 1ドル ≤ n, m ≤ 1000$
• $-10^9 ≤ A_{i,j} ≤ 10^9$ for 1ドル ≤ i ≤ n$ and 1ドル ≤ j ≤ m$

서브태스크

힌트