Беги, Альф! Беги!

면접 대비

시간 제한2초메모리 제한1024 MB

요약

n×3 격자에서 아래 세 칸 중 하나로 이동하며 벽을 피해 지나갈 때 모을 수 있는 동전의 최댓값을 구한다.

난이도: 보통10점 중 4점
유형: 동적 계획법, 배열
정답자: 아직 제출이 없습니다

문제

Прямо сейчас Альфу снится кошмар. В нем он бежит по дороге с препятствиями, на которой, ко всему прочему, разбросаны монеты.

Дорога представляет из себя таблицу $n \times 3$ , в клетках которой либо ничего нет, либо находится стена, либо монета. Альф бежит вдоль стороны длиной $n$ . Начинает он бежать из первой строки (то есть у него есть три варианта начала, он может выбрать любой из них) и бежит до тех пор, пока не врежется в стену, либо не пробежит дорогу целиком (не окажется в строчке $n$ ).

Пусть сейчас Альф стоит в cтроке $x$ и столбце $y$ --- $(x;y)$ , тогда он может попасть в три возможные клетки: $(x+1; y-1)$ , $(x+1; y)$ , $(x+1; y+1)$ , если конечно новая клетка не выходит за пределы дороги, и в ней не находится стена. Так как все обитатели планеты Мелмак умеют контролировать свои сны, Альф смог получить карту дороги. Теперь он хочет узнать, какое наибольшее количество монет можно собрать к концу забега.

Так как контроль сна отнимает у Альфа много сил, он просит вас написать программу, которая по карте сможет определить наибольшее количество монет, которое можно собрать за один забег.

입력

В первой строке входного файла задано число $n$ ( $1 \le n \le 10^4$ ) --- количество строк в таблице. В следующих $n$ строках дано по три символа $с$ , характеризующие данную строку таблицы. $c$ равен <<.>>, если клетка пустая, <<C>>, если в этой клетке монета, и <<W>>, если стена. Если в первой строке во всех клетках находятся стены, Альф заканчивает забег сразу.

출력

В выходной файл выведите одно число --- наибольшее количество монеток, которые можно собрать.

예제2

예제 1
입력
```
5
W.W
C.C
WW.
CC.
CWW
```
예상 출력
```
3
```
예제 2
입력
```
4
W.W
CWC
W.W
CWW
```
예상 출력
```
2
```