25708번 - 만남의 광장

문제

인하대학교의 마스코트인 인덕이가 사는 인경호는 인하대학교 학생이 아니여도 주변에 거주하는 사람들이 산책로로 이용할 수 있다. 인하대학교는 인경호에서 산책하는 사람들이 많은 것을 알고 이들을 위해 인경호 근처에 적당한 녹지를 골라 만남의 광장을 만들기로 하였다.

만남의 광장은 위 그림과 같이 N × M 크기의 녹지에 각각 다른 행을 골라 가로 방향으로 2개, 각각 다른 열을 골라 세로 방향으로 2개의 직선으로 뻗은 4개의 길을 놓아 만든다. 녹지의 i행 j열의 칸에는 가치 d_ij가 정해져있다.

인하대학교는 녹지에 만남의 광장을 만들 때 광장의 아름다움을 최대화하려고 한다. 이때, 광장의 아름다움이란 4개의 길에 둘러싸인 직사각형 꼴 영역에 포함된 녹지인 칸의 개수에 길이 깔린 모든 칸의 가치를 더한 값이다. 광장의 아름다움은 0보다 작을 수 있다.

만남의 광장을 만들기 위해 고른 녹지의 크기와 모든 칸 각각의 가치가 주어질 때, 만남의 광장의 아름다움을 최대화했을 때의 아름다움을 출력하여라.

입력

첫 번째 줄에 만남의 광장을 만들 녹지의 크기 N과 M이 공백으로 구분되어 주어진다.

두 번째 줄부터 N개의 줄에 걸쳐 녹지의 각 칸에 길을 놓을 때 광장의 아름다움에 영향을 끼치는 정도 d_ij가 M개씩 공백으로 구분되어 주어진다.

출력

주어진 녹지에 만남의 광장을 만들 때 광장의 아름다움의 최댓값을 출력한다.

제한

• 2 ≤ N ≤ 100
• 2 ≤ M ≤ 100
• -1,000 ≤ d_ij ≤ 1,000

힌트

• Python 사용자는 PyPy로 제출하는 것을 권장한다.