Description

Original Source: NOI 2001

The generals at the 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, where each cell is either a mountain (denoted by H) or a plain (denoted by P), as shown in the figure below. On each plain cell, at most one artillery unit can be deployed (artillery units cannot be deployed on mountain cells). The attack range of an artillery unit on the map is illustrated by the black areas in the figure:

If an artillery unit is deployed on the plain cell marked in gray, the black grids in the figure represent the areas it can attack: two cells to the left and right horizontally, and two cells above and below vertically. Other white grids in the figure are outside its attack range. As seen from the figure, the artillery's attack range is not affected by terrain.
Now, the generals are planning how to deploy the artillery units to maximize the number of our artillery units within the entire map area while preventing friendly fire (ensuring no two artillery units can attack each other, meaning no artillery unit is within the attack range of any other artillery unit).

Input Format

The first line contains two positive integers separated by a space, representing $N$ and $M$;
The next $N$ lines each contain a continuous string of $M$ characters (P or H), with no spaces in between. These represent the data for each row of the map in order.

Output Format

A single line containing an integer $K$, representing the maximum number of artillery units that can be deployed.

Sample 1

5 4
PHPP
PPHH
PPPP
PHPP
PHHP

6

Data Range and Hint

$N \le 100, M \le 10$.