종이 접기
시간 제한2초메모리 제한128 MB
N행 M열의 정수 격자를 행 또는 열 경계를 따라 여러 번 접어 겹치는 칸의 값을 더할 때, 어느 칸에서든 얻을 수 있는 최댓값을 구합니다.
문제
직사각형 종이가 있다. 종이는 (N)행 (M)열의 1×1 칸으로 나뉘어 있고, 각 칸에는 정수가 하나씩 적혀 있다.
종이는 여러 번 접을 수 있다. 한 번 접을 때마다 서로 이웃한 두 행 사이 또는 두 열 사이의 선을 골라 한쪽 부분을 다른쪽 위로 접는다. 접은 뒤 같은 위치에 겹친 칸의 값은 그 칸들에 적혀 있던 값의 합이 된다.
가능한 모든 접는 방법을 고려했을 때, 접힌 종이에 나타날 수 있는 칸의 값 중 최댓값을 구하시오.
입력
첫째 줄에 종이의 세로 크기 (N)과 가로 크기 (M)이 주어진다. (N)과 (M)은 12 이하의 자연수이다.
둘째 줄부터 (N)개의 줄에는 각 줄마다 (M)개의 정수가 주어진다. 각 정수의 절댓값은 100 이하이다.
출력
가능한 칸의 값 중 최댓값을 한 줄에 출력한다.