던전

Dungeon Crawl: Paper Soup가 최근 가장 인기 있는 게임이 되었고, 여러분도 이 게임을 해 볼 참이다. 게임은 $N$행 $M$열의 직사각형 필드에서 진행된다. 각 칸은 다음 중 하나이다.

• 빈 칸 ‘.’
• 벽 ‘#’
• 동전 칸 ‘o’
• 폭발 지뢰 칸 ‘X’
• 시작 칸 ‘S’

첫 행과 마지막 행, 첫 열과 마지막 열에는 벽만 있다. 플레이어는 벽 칸을 통과해 이동할 수 없다. 필드에는 시작 칸이 하나 이상 있다. 게임이 시작되면 플레이어는 ‘S’로 표시된 시작 칸 중 하나에 놓인다.

이 던전은 시야가 제한되어 있다. 플레이어는 현재 위치를 중심으로 한 $3 \times 3$ 정사각형만 볼 수 있다. 플레이어에게 지뢰 칸과 시작 칸은 빈 칸처럼 보인다.

한 번의 이동으로 북, 남, 동, 서 방향의 인접한 칸 중 한 곳으로 갈 수 있다. 플레이어가 동전 칸에 들어가면 동전을 모으고 그 동전은 사라진다. 플레이어가 폭발 지뢰 칸에 들어가면 던전이 무너지고, 플레이어는 그때까지 모은 동전을 모두 잃은 채 게임이 끝난다.

여러 온라인 공략 글을 뒤져서 이 던전의 지도를 구했다. 플레이어가 어느 시작 칸에서 출발할지는 알 수 없지만, 플레이어는 반드시 시작 칸 중 하나에서 출발한다. 시작 위치를 모르는 상태에서 최적으로 플레이할 때, 반드시 얻을 수 있는 동전의 최대 개수는 얼마인가?

첫 줄에 지도의 행 수 $N$과 열 수 $M$이 주어진다. 다음 $N$개의 줄에는 위에서 설명한 표기법에 따라 각 줄마다 $M$개의 문자로 지도가 주어진다.

시작 위치를 모르는 상태에서 이 지도에서 반드시 얻을 수 있는 동전의 최대 개수를 한 개의 수로 출력한다.

$S$를 지도 위에서 가능한 시작 칸의 개수라고 하자.

$N ≤ 400$, $M ≤ 400$, $S ≤ 60$.