윈도우 쇼핑

당신은 새로 지은 쇼핑몰의 층 배치를 설계하는 일을 돕는다. 쇼핑몰은 칸으로 이루어진 직사각형 격자이다. 두 칸이 변을 공유하면 인접한 칸이다. 각 칸은 빈 칸, 기둥, 에스컬레이터 중 하나이다. 에스컬레이터는 정확히 두 개이며, 하나는 위층으로, 다른 하나는 아래층으로 간다. 에스컬레이터는 작아서 손님이 층을 바꾸지 않고도 그 칸을 자유롭게 지나갈 수 있다.

빈 칸 중 일부를 골라 상점을 짓는다. 나머지 빈 칸과 두 에스컬레이터 칸은 손님이 다닐 수 있는 칸이다. 다닐 수 있는 칸을 거쳐 두 에스컬레이터에서 모두 도달할 수 있는 빈 칸은 복도가 된다. 상점과 복도 사이의 변에는 쇼윈도를 설치할 수 있다.

배치가 끝난 뒤에도 두 에스컬레이터 모두에서 도달할 수 없는 빈 칸이 남을 수 있다. 이런 칸은 복도가 아니므로 주변에 쇼윈도를 설치할 수 없다. 에스컬레이터도 복도가 아니므로 에스컬레이터의 어느 변에도 쇼윈도를 설치할 수 없다.

최근 고객 분석 보고서에 따르면 쇼핑몰의 수익은 내부 쇼윈도 수에 비례해 늘어난다. 설치할 수 있는 쇼윈도의 최대 개수를 구하라.

첫 줄에 격자의 행 수와 열 수를 나타내는 양의 정수 $r$과 $c$ ($4 \le r \cdot c \le 99$)가 주어진다. 이어지는 $r$개 줄에는 길이가 $c$인 문자열이 한 줄씩 주어진다. 각 문자는 다음 중 하나이다.

• . 빈 칸
• # 기둥
• U 위층 에스컬레이터 (정확히 하나)
• D 아래층 에스컬레이터 (정확히 하나)

처음에는 모든 빈 칸이 두 에스컬레이터 모두에서 도달 가능하다는 것이 보장된다.

설치할 수 있는 쇼윈도의 최대 개수를 정수 하나로 출력한다.

첫 번째 예제에서 쇼윈도를 설치하는 최적 방법 중 하나이다. 파란 칸은 상점이고, 빨간 변은 쇼윈도이다.