Tracks in the Snow

In a forest there is a rectangular meadow that was covered with fresh snow in the morning (left in the figure below).

Rabbits and foxes that live in the forest cross the meadow and leave tracks in the snow. Every animal enters at the upper-left corner and leaves at the lower-right corner. In between it may wander back and forth, even crossing its own tracks. At most one animal is on the meadow at any moment, and no animal enters more than once.

Model the meadow as a grid of square cells. In a single step an animal moves to an orthogonally adjacent cell (never diagonally, never skipping a cell). When an animal steps onto a cell, its track covers every earlier track in that cell, so only the most recent animal's track is visible there.

For example, a rabbit first crosses from the top-left to the bottom-right (middle in the figure). Afterwards a fox crosses, partly covering the rabbit's tracks (right in the figure):

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

You are given the state of the meadow at some later time: for every cell you know whether a track is visible and, if so, whether it was left by a rabbit or by a fox (the right panel above). Determine the minimum number $N$ of animals that must have crossed the meadow to produce the given pattern of tracks.

The first line contains two integers $H$ and $W$ — the height and width of the meadow. Each of the next $H$ lines contains exactly $W$ characters describing one row of the map: . is untouched snow, R is a cell whose topmost track belongs to a rabbit, and F is a cell whose topmost track belongs to a fox. At least one cell carries a track.

Print a single integer: the minimum number $N \ge 1$ of animals that could have left the tracks shown in the input.

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