Description

The generals at headquarters plan to deploy their artillery units on an $N\times M$ grid map.

An $N\times M$ map consists of $N$ rows and $M$ columns. Each cell may be mountain terrain (denoted by $\texttt{H}$) or plain terrain (denoted by $\texttt{P}$), as shown below.

At most one artillery unit can be placed on each plain cell (artillery cannot be placed on mountains). The attack range of one artillery unit is shown by the black area in the figure:

If an artillery unit is deployed on the gray plain cell, then the black cells in the figure mark the area it can attack: two cells to the left and right horizontally, and two cells up and down vertically.

All other white cells in the figure are out of range. As can be seen, the artillery’s attack range is not affected by terrain.

Now the generals are planning how to deploy the artillery units. Under the constraint of preventing friendly fire (ensuring that no two artillery units can attack each other, i.e., no artillery unit lies within the attack range of any other), determine the maximum number of our artillery units that can be placed on the entire map.

Input Format

The first line contains two positive integers separated by a space, representing $N$ and $M$.

The next $N$ lines each contain exactly $M$ consecutive characters, in order representing each row of the map.

Output Format

Output a single integer on one line, the maximum number of artillery units that can be placed.

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

6

Hint

Constraints: For $100\%$ of the testdata, $1 \leq N \le 100$, $1 \leq M \le 10$. The characters are guaranteed to contain only P and H.

Translated by ChatGPT 5