싱가포르 관광

관광객이 싱가포르 지도를 들고 있다. 지도는 $R \times C$ 크기의 격자이고 $1 \le R, C \le 20$이다. 각 칸은 다음 중 하나다.

• ~(물결표)는 물이다.
• .는 땅이다.
• 2부터 9까지의 숫자는 관광지다.
• C는 창이 공항이다.

아래 지도는 C 한 곳과 5, 6으로 표시된 관광지 두 곳이 있는 $3 \times 5$ 격자다.

~.~.~
6.~5.
~..C~

관광지는 $N$곳 있고 $0 \le N \le 14$이다. 관광지 $i$에 적힌 숫자가 그 관광지의 만족도 $S_i$이며 $2 \le S_i \le 9$이다. 5라고 적힌 관광지는 $S_i = 5$이다. 관광객이 관광지 $i$를 방문하면 $S_i$점을 얻는다.

관광객은 상하좌우 네 방향으로 한 칸씩 움직이고 물 칸에는 들어갈 수 없다. 물이 아닌 칸은 땅이든 관광지든 창이 공항이든 모두 지나갈 수 있다. 싱가포르는 정비가 잘 된 도시라서 물이 아닌 어느 칸에서 출발해도 물이 아닌 모든 칸에 도달한다. 이동은 힘들기 때문에 한 칸 움직일 때마다 만족도가 $2$점 깎인다. 행과 열 번호는 0부터 센다. 위 지도에서 2행 3열의 C에서 1행 0열의 6까지 최단 경로로 걸으면 네 번 움직이므로 $4 \times (-2) = -8$점이다.

관광객은 창이 공항 C에 내려서 가고 싶은 관광지를 돌고 다시 C로 돌아와 비행기를 탄다. 물이 아닌 칸은 몇 번이든 다시 지나갈 수 있지만, 각 관광지의 만족도는 한 번만 얻는다. 주어진 지도에서 관광객이 얻는 만족도의 최댓값은 얼마인가?

위 지도에서 C → 6 → 5 → C 순서로 돌면 $4 \times (-2) + 6 + 5 \times (-2) + 5 + 1 \times (-2) = -9$점이다. C → 5 → C 순서로 돌면 $1 \times (-2) + 5 + 1 \times (-2) = 1$점이고 이것이 모든 경로 중 최댓값이다. 관광객은 걸어갈 값어치가 없다고 보고 6을 건너뛴다.

첫 줄에 정수 $R$과 $C$가 공백 하나를 사이에 두고 주어진다. 다음 $R$개의 줄에는 각각 정확히 $C$개의 문자가 주어진다. 입력에 C는 정확히 하나 있고 관광지는 0곳 이상 14곳 이하다.

관광객이 얻는 만족도의 최댓값을 정수 하나로 출력한다. 관광지를 한 곳도 방문하지 않아도 되므로 답은 음수가 되지 않는다.