격자 연결하기

면접 대비

시간 제한1초메모리 제한1024 MB

요약

N×M 격자의 각 칸에 정수가 적혀 있을 때, 두 칸을 골라 그 사이 최단 경로에 있는 칸 값의 합을 최대로 구합니다.

문제

각 격자에 정수가 적힌 $N\times M$ 크기의 격자판이 있다. 격자판 점수는 격자 2개를 고른 뒤 최단 경로로 연결했을 때, 연결된 경로에 있는 격자들에 적힌 수의 합으로 계산한다.

최단 경로가 여러 개면 그중 아무 경로를 골라도 된다. 연결된 경로에는 고른 두 격자도 포함된다. 같은 위치의 격자를 두 번 고를 수도 있는데, 이때는 그 격자의 수를 한 번만 더한다.

임의의 두 격자를 골랐을 때 얻을 수 있는 격자판 점수의 최댓값을 구한다.

첫째 줄에 격자판의 세로 크기 $N$ 과 가로 크기 $M$ 이 공백으로 구분되어 주어진다. $(1\leq N,M\leq 1,000)$

둘째 줄부터 $N$ 줄에 걸쳐 격자의 점수 $A_{ij}$ 가 공백으로 구분되어 주어진다. $(|A_{ij}|\leq 1,000;\ 1\leq i\leq N;\ 1\leq j\leq M)$

두 격자를 골랐을 때 얻을 수 있는 격자판 점수의 최댓값을 출력한다.

$(r, c)$ 를 기준으로 $(3, 1)$ 위치의 격자와 $(2, 4)$ 위치의 격자를 고르면 $4, 5, 7, -3, 6$ 을 선택하여 $19$ 점을 얻는다.

예제 1

입력

4 4
-1 -3 -2 -1
2 1 -3 6
4 5 7 -4
-4 -6 -3 -3

예상 출력