격자 덮기
시간 제한1초메모리 제한256 MB
왼쪽 위 칸에서 오른쪽 아래 칸까지 모서리로 이어지는 직사각형들을 배치해 덮인 칸 숫자의 합을 최대로 합니다.
문제
명우는 각 칸에 정수가 하나씩 적힌 행 열 격자를 가지고 있다. 크기가 제각각인 직사각형 판도 여러 장 있어서, 다음 규칙에 따라 격자를 판으로 덮으려고 한다.
- 판은 격자와 평행하게, 격자 안에 놓는다. 한 칸의 일부만 덮는 것은 허용되지 않는다.
- 첫 번째 판은 1행 1열 칸을 반드시 포함한다.
- 두 번째 판부터는 바로 앞에 놓은 판의 오른쪽 아래 꼭짓점에 닿게 놓아야 하고, 두 판의 변이 서로 닿아서는 안 된다. 즉 앞의 판이 행 열 칸에서 끝났다면 다음 판은 행 열 칸에서 시작한다.
- 마지막 판은 행 열 칸을 반드시 포함한다.
아래 그림은 8행 8열 격자를 규칙대로 덮은 예이다.
점수는 판에 덮인 칸에 적힌 정수를 모두 더한 값이다. 어떤 판에도 덮이지 않은 칸은 점수에 들어가지 않는다. 격자가 주어질 때 명우가 얻을 수 있는 가장 큰 점수를 구하여라.
입력
첫 줄에 두 자연수 , 가 주어진다.
다음 개의 줄에는 각 행의 값이 개씩 공백으로 구분되어 주어진다. 각 값의 절댓값은 이하이다.
이다.
출력
규칙대로 덮어서 얻을 수 있는 가장 큰 점수를 한 줄에 출력한다.