Maximum Artillery Placement

The headquarters generals plan to deploy their artillery on an \(N\times M\) grid map. The grid consists of \(N\) rows and \(M\) columns. Each cell is either a mountain (denoted by H) or a plain (denoted by P). An artillery unit can only be deployed on a plain cell (mountain cells are not allowed).

When deployed on a plain cell at position \((i,j)\), the artillery unit attacks the cells that are exactly one or two units away horizontally and vertically. More formally, if an artillery is placed in cell \((i,j)\), then it can attack cells \((i, j-2)\), \((i, j-1)\), \((i, j+1)\), \((i, j+2)\) in the same row, and cells \((i-2, j)\), \((i-1, j)\), \((i+1, j)\), \((i+2, j)\) in the same column. Note that the attack range is not affected by the terrain.

To avoid friendly fire, the deployment must ensure that no two artillery units are placed such that one is in the attack range of another. Your task is to determine the maximum number of artillery units that can be deployed on the map under these constraints.

Note: Any mathematical formulas must be written using LaTeX format. For example, the grid is represented as \(\{1,2,\dots, N\} \times \{1,2,\dots, M\}\) and the conditions for attack are expressed as:

[ \text{If an artillery is placed at } (i,j), \text{ then no other artillery can be placed at } (i,j') \text{ where } |j-j'| \in {1,2}, ] [ \text{and } (i',j) \text{ where } |i-i'| \in {1,2}. ]

inputFormat

The first line contains two integers \(N\) and \(M\) (for example, \(1 \leq N,M \leq 10\)). The following \(N\) lines each contain a string of length \(M\) consisting only of the characters P and H, representing plains and mountains respectively.

outputFormat

Output a single integer: the maximum number of artillery units that can be deployed on the grid without any two being in each other’s attack range.

sample

3 3
PPP
PHP
PPP

3