#1827 자리배치

13  10 s   128 MB  

Description

ANSI의 신입생들은 스터디 시간 마다 항상 제자리에 있지 못하고 돌아다니기를 좋아한다. 오늘은 마침 재학생 선배들이 자리를 비웠고, 오기로 했던 용균이도 차가 막혀서 늦게 오게 되자, 모든 신입생들이 자리에 앉아 있지 않고 신이 나서 뛰어 놀고 있었다.

그러던 도중에 마침 용균이가 도착했고, 아무도 자리에 앉아 있지 않은 것을 보고나서 화가 나버린 용균이는 화를 내며 신입생들에게 자리에 앉으라고 지시하였다.

화가 난 용균이는 신입생들에게 벌금을 걷기로 하였는데, 벌금은 모든 학생들이 자리에 앉을 때 까지 걸리는 시간에 비례하여 걷기로 했다. 즉, 마지막 학생이 앉았을 때 걸린 시간에 비례하여 신입생들을 벌금을 내게 되는 것이다.

당연히 어느 누구도 벌금을 많이 내는 것을 좋아하진 않지만, 많은 신입생들이 용균이를 무서워 하기 때문에 어쩔 수 없이 벌금을 내야 한다. 허나, 벌금을 최소한 내기를 바란다. 따라서 학생들은 최대한 머리를 짜내어 내는 벌금의 양을 최소화 하고자 한다.

ANSI가 스터디를 하고 있는 강의실은 격자구조로 이루어져 있고, 각각의 칸마다 신입생들과 컴퓨터가 위치해 있다. 컴퓨터는 한 칸에 하나만 존재할 수 있으며, 신입생의 경우 한 칸에 두 명 이상의 신입생이 동시에 존재할 수 있다. 신입생은 한 번에 상하좌우 한 칸으로 이동이 가능하며, 이동 할 때는 1의 시간이 걸린다. 컴퓨터가 있는 자리에 앉을 수 있는 신입생은 한명밖에 없으며, 신입생은 아무 컴퓨터에나 앉을 수 있다. 모든 신입생들이 동시에 움직인다고 가정한다.

현재 강의실의 정보가 들어 올 때, 모든 신입생이 컴퓨터가 있는 자리에 도착하는 최소의 시간을 출력하는 프로그램을 작성하라.

Input

첫 번째 줄에는 강의실의 높이와 너비를 뜻하는 $N$, $M$ $(1 \leq N,M \leq 50)$이 공백을 사이에 두고 입력된다.

그 다음 줄에는 $N \times M$의 격자로 이루어진, 강의실의 정보가 입력이 된다. 한 개의 문자는 격자의 한 칸을 뜻하며, .은 비어있는 공간을 의미하고, 대문자 C는 컴퓨터가 있는 자리를 의미하며, 대문자 S는 신입생들을 의미한다. 대문자 X는 갈수 없는 곳을 뜻한다. 컴퓨터의 대수와 신입생의 명수는 100이하이며, 컴퓨터의 대수는 신입생의 수보다 같거나 많다.

Output

모든 신입생들이 자리에 앉을 때 가능한 최소의 시간을 출력한다. 불가능한 경우는 없다고 가정한다.

Sample Input

Sample Output

3 4
C..S
C..S
C..S
3