행렬 원소 합 최대화

시간 제한2초메모리 제한256 MB

요약

행과 열을 회전하고 행과 열의 부호를 뒤집어 전체 합이 가장 커지도록 행렬을 변형합니다.

문제

R행 C열 행렬이 주어진다. 각 칸에는 정수가 하나씩 적혀 있고, 다음 네 가지 연산을 원하는 순서로 몇 번이든 사용할 수 있다.

표기법	뜻
`rotR i k`	i번째 행을 오른쪽으로 k칸 회전시킨다. ( $1 \le i \le R$ , $1 \le k < C$ )
`rotC j k`	j번째 열을 아래로 k칸 회전시킨다. ( $1 \le j \le C$ , $1 \le k < R$ )
`negR i`	i번째 행의 모든 원소에 $-1$ 을 곱한다. ( $1 \le i \le R$ )
`negC j`	j번째 열의 모든 원소에 $-1$ 을 곱한다. ( $1 \le j \le C$ )

행렬 $\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \end{pmatrix}$ 에 각 연산을 한 번씩 적용한 결과는 다음과 같다.

rotR 3 1을 적용하면 $\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 9 & 7 & 8 \end{pmatrix}$ 이 된다.
rotC 1 2를 적용하면 $\begin{pmatrix} 4 & 2 & 3 \\ 7 & 5 & 6 \\ 1 & 8 & 9 \end{pmatrix}$ 가 된다.
negR 2를 적용하면 $\begin{pmatrix} 1 & 2 & 3 \\ -4 & -5 & -6 \\ 7 & 8 & 9 \end{pmatrix}$ 가 된다.
negC 2를 적용하면 $\begin{pmatrix} 1 & -2 & 3 \\ 4 & -5 & 6 \\ 7 & -8 & 9 \end{pmatrix}$ 가 된다.

연산을 마친 뒤 행렬의 모든 원소의 합이 가장 클 때, 그 합을 구하라.

첫 줄에 두 자연수 R, C ( $1 \le R, C \le 100$ )가 공백으로 구분되어 주어진다.

다음 R개의 줄에 각각 C개의 정수가 공백으로 구분되어 주어진다. 각 정수의 절댓값은 $10^4$ 이하이다.

첫 줄에 얻을 수 있는 모든 원소의 합의 최댓값을 출력한다. 사용한 연산의 목록은 출력하지 않는다.

예제 1

입력

3 4
1 -2 5 200
-8 0 -4 -10
11 4 0 100

예상 출력