시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB437897131.140%

문제

형택이는 직사각형 종이를 가지고 있다. 이 종이는 1×1크기의 칸으로 나누어져 있고, 각 칸에는 숫자가 적혀 있다.

형택이는 종이를 적절히 접는다. 종이를 접을 때는 두 행 또는 두 열의 사이를 접는다. 이렇게 종이를 접고 나면, 겹치는 칸이 있다. 이때, 겹친 칸의 수는 원래 각 칸에 적혀 있는 두 수를 더한 것이다.

형택이가 종이를 적절히 접어서 나올 수 있는 각 칸에 적혀 있는 수 중 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 종이의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 12보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 종이의 각 칸에 적혀 있는 수가 주어진다. 이 값은 절댓값이 100보다 작거나 같은 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

예제 입력 1

4 4
1 -1 -1 1
-1 -1 -1 -1
-1 -1 -1 -1
1 -1 -1 1

예제 출력 1

4

예제 입력 2

2 3
1 1 1
1 1 1

예제 출력 2

6

예제 입력 3

2 2
1 -1
1 -1

예제 출력 3

2

예제 입력 4

1 1
0

예제 출력 4

0

예제 입력 5

3 4
20 13 -2 100
-12 0 4 -3
4 1 -36 21

예제 출력 5

131

출처

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