cho.sh

행렬 원소 합 최대화

아직 제출이 없습니다시간 제한2초메모리 제한256 MB

문제

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

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

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

  • rotR 3 1을 적용하면 (123456978)\begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 9 & 7 & 8 \end{pmatrix}이 된다.
  • rotC 1 2를 적용하면 (423756189)\begin{pmatrix} 4 & 2 & 3 \\ 7 & 5 & 6 \\ 1 & 8 & 9 \end{pmatrix}가 된다.
  • negR 2를 적용하면 (123−4−5−6789)\begin{pmatrix} 1 & 2 & 3 \\ -4 & -5 & -6 \\ 7 & 8 & 9 \end{pmatrix}가 된다.
  • negC 2를 적용하면 (1−234−567−89)\begin{pmatrix} 1 & -2 & 3 \\ 4 & -5 & 6 \\ 7 & -8 & 9 \end{pmatrix}가 된다.

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

입력

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

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

출력

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