눈 위의 발자국

숲속에 직사각형 모양의 풀밭이 있고, 아침에 갓 내린 눈이 이 풀밭을 덮었다(아래 그림의 왼쪽).

숲에 사는 토끼와 여우가 풀밭을 가로지르며 눈 위에 발자국을 남긴다. 모든 동물은 왼쪽 위 칸에서 들어와 오른쪽 아래 칸으로 나간다. 그 사이에는 자기 발자국을 다시 밟더라도 자유롭게 앞뒤로 돌아다닐 수 있다. 어느 순간에도 풀밭 위에는 동물이 최대 한 마리만 있으며, 같은 동물이 두 번 들어오지는 않는다.

풀밭을 정사각형 칸으로 나누어 생각한다. 한 걸음에 동물은 상하좌우로 인접한 칸으로만 이동하며(대각선 이동이나 칸 건너뛰기는 없다), 어떤 칸에 들어서면 그 칸에 있던 이전 발자국을 모두 덮어 가장 마지막 동물의 발자국만 보이게 된다.

예를 들어 먼저 토끼가 왼쪽 위에서 오른쪽 아래로 지나가고(그림의 가운데), 그다음 여우가 지나가며 토끼의 발자국 일부를 덮은 모습은 다음과 같다(그림의 오른쪽).

........ RRR..... FFR.....
........ ..RRR... .FRRR...
........ ..R..... .FFFFF..
........ ..RRRR.R ..RRRFFR
........ .....RRR .....FFF

어느 시점에 관찰한 풀밭의 상태가 주어진다. 각 칸에 발자국이 보이는지, 보인다면 토끼의 것인지 여우의 것인지를 알 수 있다(위 그림의 오른쪽). 주어진 발자국 무늬를 만들기 위해 풀밭을 가로질러야 했던 동물의 최소 마릿수 $N$을 구하여라.

첫째 줄에 풀밭의 높이 $H$와 너비 $W$가 주어진다. 이어지는 $H$개의 줄에는 각각 정확히 $W$개의 문자가 주어져 지도의 한 행을 나타낸다. .은 밟지 않은 눈, R은 가장 위에 보이는 발자국이 토끼의 것인 칸, F는 가장 위에 보이는 발자국이 여우의 것인 칸이다. 발자국이 있는 칸은 적어도 하나 존재한다.

입력에 주어진 발자국을 남길 수 있는 동물의 최소 마릿수 $N \ge 1$을 정수 하나로 출력한다.

• $1 \le H, W \le 4000$