시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB55171528.302%

문제

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$

서브태스크

번호배점제한
15

$1 ≤ n, m ≤ 2$

210

$n = 1$

315

$1 ≤ n, m ≤ 100$

415

$1 ≤ n, m ≤ 300$

525

$0 ≤ A_{i,j} ≤ 10^9$ for $1 ≤ i ≤ n$ and $1 ≤ j ≤ m$

630

No additional restrictions

예제 입력 1

2 2
8 1
3 4

예제 출력 1

15

In this example, you choose 8, 3, 4 to form an L.

This testcase is valid for subtasks 1, 3, 4, 5 and 6.

예제 입력 2

1 8
-2 -1 8 -2 9 0 -2 1

예제 출력 2

15

You draw a line covering 8, -2 and 9.

This testcase is valid for subtasks 2, 3, 4, and 6.

채점 및 기타 정보

  • 예제는 채점하지 않는다.