30511번 - 꼬치구이

문제

방학을 맞아 세종이와 가족들은 캠핑을 하러 갔다. 열심히 놀다 보니 어느새 저녁이 되었고 캠핑의 꽃인 캠프파이어를 하려고 한다.

세종이는 모닥불에 구워 먹기 위해 꼬치에 여러 재료를 꽂고 있다. 재료를 꽂고 있던 세종이를 본 세종이의 어머니는 여러 가지 식재료를 골고루 먹기 위해 고기, 파, 버섯을 각각 하나씩 꼬치에 꽂으라고 하셨다. 하지만 편식쟁이 세종이는 버섯을 싫어해서 꼬치에 파와 고기만 꽂고 싶었다. 세종이는 엄마 몰래 버섯 없는 꼬치를 만들기 위해 꼬치에 고기와 파를 하나씩 꽂고 나서 마지막으로 버섯을 꽂는 척만 하고 그대로 모닥불에 꼬치를 굽기로 했다.

꼬치의 재료는 $N\times M$ 크기의 격자 형태로 놓여 있다. 격자의 각 칸에 고기, 파, 버섯 중 하나가 들어있는 것으로 생각할 수 있다. 꼬치를 만들 때는 가로, 세로 또는 대각선으로 연속된 세 재료를 선택해 그 순서대로 꽂아야 한다. 이때 꽂는 척을 하기 위해 버섯은 꼬치의 맨 끝에 위치해야 한다. 또 고기나 파 하나가 여러 개의 꼬치에 꽂히면 안 되지만, 버섯 하나를 여러 개의 꼬치를 만드는 데에 사용하는 것은 가능하다.

세종이가 만들 수 있는 버섯 없는 꼬치구이 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 격자의 크기를 나타내는 두 정수 $N,ドル $M$이 공백으로 구분되어 주어진다. $(1\le N,M\le 100)$

둘째 줄부터 $N$개의 줄에 걸쳐 길이가 $M$인 문자열이 주어진다. $i$번째 문자열의 $j$번째 문자는 격자의 $i$행 $j$열에 들어 있는 재료를 의미한다. 각 문자열은 S, G, M으로만 구성되어 있으며, 각각 고기, 파, 버섯을 의미한다.

출력

첫째 줄에 세종이가 만들 수 있는 버섯 없는 꼬치구이 개수의 최댓값을 출력한다.

제한

힌트