시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB122706270.455%

문제

여러 방들로 둘러싸인 구역을 탈출해야 한다. 알맞은 비밀번호를 입력하면 탈출할 수 있다.

구역의 지도는 $N \times M$ 크기의 격자판으로 나타낼 수 있으며 각 칸은 방을 의미하고 각 칸에는 0부터 9까지의 숫자가 적혀있는데 이는 해당하는 방에 적힌 숫자를 의미한다.

상하좌우 4가지 방향으로만 움직일 수 있으며, 0이 적힌 방은 들어갈 수 없다.

비밀번호의 힌트는 다음과 같다.

  1. 임의의 방에서 다른 방으로 이동할 때는 항상 두 방 사이의 최단 경로로 이동한다.
  2. 1번을 만족하는 경로 중 가장 긴 경로의 시작 방과 끝 방에 적힌 숫자의 합

만약 위 2가지 조건을 만족하는 경로가 여러 개라면, 시작 방과 끝 방에 적힌 숫자의 합이 가장 큰 값이 비밀번호가 된다.

시작 방과 끝 방은 동일한 위치일 수도 있다.

<예시> $5 \times 5$ 형태의 지도가 주어질 때, 위의 2가지 조건을 만족하는 경로는 다음과 같다.

이 때 비밀번호가 무엇인지를 구해라.

만약 비밀번호를 만들 수 없는 경우 0을 출력한다.

입력

첫줄에 지도의 세로 크기 $N$($1 \le N \le 50$), 가로 크기 $M$($1 \le M \le 50$)이 공백을 두고 주어진다.

둘째 줄부터 $N$줄에 걸쳐 각 방들의 정보 $A$($0 \le A \le 9$)가 공백을 두고 주어진다.

출력

올바른 비밀번호를 출력한다.

예제 입력 1

5 5
1 2 3 4 5
0 0 4 0 0
0 0 5 0 0
8 7 6 7 8
9 0 7 0 0

예제 출력 1

14

예제 입력 2

2 2
1 2
3 4

예제 출력 2

5

예제 입력 3

5 6
2 0 7 4 0 2
0 8 5 0 3 0
6 9 5 7 7 2
6 9 3 9 9 7
0 8 7 4 0 3

예제 출력 3

7