시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 116 45 24 32.877%

문제

크기가 N×M인 배열 A가 있을 때, 다음과 같은 방법을 이용해서 크기가 (N-1)×(M-1)인 배열 B를 만들 수 있다.

  • B[i][j] = A[i][j] + A[i+1][j] + A[i+1][j+1] + A[i][j+1] (1 ≤ i < N, 1 ≤ j < M)

배열의 값은 배열의 모든 원소를 합한 값이다.

배열 A에서 임의의 두 행이나 임의의 두 열의 위치를 교환할 수 있다. 배열 A에서 교환을 최대 1번 수행해서 만들 수 있는 배열 B의 값의 최댓값을 구해보자.

입력

첫째 줄에 배열 A의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 배열의 원소가 주어진다. 배열은 정수로만 이루어져 있다.

출력

만들 수 있는 배열 B의 값 중 최댓값을 출력한다.

제한

  • 2 ≤ N, M ≤ 1,000
  • -1,000 ≤ Ai,j ≤ 1,000

예제 입력 1

3 3
9 8 7
3 2 1
6 5 4

예제 출력 1

92

1번 행과 2번 행을 교환하는 것이 최대이다.

예제 입력 2

3 4
1 2 1 1
2 1 1 2
2 1 1 1

예제 출력 2

34

1번 열과 3번 열을 교환하는 것이 최대이다.

예제 입력 3

3 3
1 1 1
1 2 1
1 1 1

예제 출력 3

20

교환을 하지 않는 것이 최대이다.

출처

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013