게으른 관광객은 최대한 많은 관광지를 한 발짝의 낭비없이 방문하기를 원한다.

도시의 북서쪽 지역에 위치한 호텔에서 출발하여 도시의 남동쪽의 끝으로 간후 돌아오는 길을 택하는데, 남동쪽으로 갈 때는 남쪽 혹은 동쪽으로 만 가고 , 북서쪽으로 돌아올때는 북쪽 혹은 서쪽으로만 움직일 수 있다.

도시의 지도를 본 관광객은 길이 중간 중간에 막혀 있어 이러한 길을 알아내는 것이 그렇게 쉽지 않다는 것을 알았다. 그래서 당신에게 도움을 요청했다.

이차원 도시의 지도가 주어지고 관심 지역과 막힌 지역의 정보가 주어질 때 방문가능한 최대 관심 지역수를 출력한다.

입력

첫 줄은 W,H ( 2 <= W,H <= 100 ) 가 주어진다. W 는 도시의 폭이고 ,H 은 높이이다. 다음 H 라인에는 W 개의 문자가 주어진다.

• . 갈수있는 지역
• * 관심 지역
• # 막힌 지역

• 위 왼쪽( 출발지 ) 과 아래 오른쪽( 턴닝 포인트)은 갈수 있는 지역
• 위 왼쪽( 출발지 ) 과 아래 오른쪽( 턴닝 포인트) 사이에는 H+W-2 크기의 갈수 있는 길이 존재

출력

입출력 예

입력

9 7
*........
.....**#.
..**...#*
..####*#.
.*.#*.*#.
...#**...
*........

출력

7

입력

5 5
.*.*.
*###.
*.*.*
.###*
.*.*.

출력

8

출처:Svenskt Masterskap i Programmering/Norgesmesterskapet 2004
채점 데이터:Svenskt Masterskap i Programmering/Norgesmesterskapet 2004