National Olympiad in Informatics, China, 2001

At the military headquarters, the generals are planning the deployment of their artillery squads using a map of an $N\times M$ grid. One $N\times M$ map consists of $N$ rows of $M$ columns each. A cell on the grid can represent land characterized by hills (denoted by an H) or plains (denoted by a P), as depicted by the diagram below. On each cell consisting of plains, at most one artillery squad may be positioned (artillery teams may not be placed on hills). The attack range of a single artillery squad is depicted by the black regions in the following diagram.

If a gray cell represents one artillery squad on the map, then the black cells represent the cells that it can attack - horizontally two cells each from its left to its right, and vertically two cells each from above and below it. It cannot attack any white cells on the map. It can be deduced from the diagram that the shape of the land does not impact the squad's range of attack.

Now, the generals are planning how to position the artillery so that accidental injuries are prevented (they must ensure that no two artillery teams can attack each other, and that no artillery squad may be in another artillery squad's attack range). Under this condition, they would like to know the maximum number of their artillery squads that can be positioned onto the field.

Input Specification

The first line of input contains two space-separated positive integers $N$ and $M$ $(N\le 100;M\le 10)$. The next $N$ lines each contain $M$ characters (either P or H), representing the map of the battlefield.

Output Specification

The output should contain a single integer $K$, the maximum number of artillery squads that may be positioned.

Sample Input

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

Sample Output

6

Problem translated to English by Alex.