Maximum Non-Adjacent Plant Picking

You are given a garden represented as a grid with N rows and M columns. Each cell in the grid is either a plant indicated by P or an empty space indicated by ..

Your task is to pick as many plants as possible such that no two picked plants are adjacent (including diagonally). Two cells are considered adjacent if they share any common side or corner. In mathematical terms, if you select a cell at position \((i,j)\), then you cannot select any cell \((i+dx, j+dy)\) where \(dx,dy \in \{-1,0,1\}\) and \((dx,dy) \neq (0,0)\).

Input Format: The first line of input contains two integers \(N\) and \(M\) (number of rows and columns). Each of the following \(N\) lines contains a string of length \(M\) comprising the characters P and . only.

Output Format: Output a single integer representing the maximum number of plants that can be picked such that no two picked plants are adjacent.

Example:

Input:
3 3
P.P
.P.
P.P
Output:
4

</p>

inputFormat

The first line contains two space-separated integers, \(N\) and \(M\), the number of rows and columns in the garden.

Each of the next \(N\) lines contains a string of length \(M\) where each character is either P (indicating a plant) or . (indicating an empty cell).

outputFormat

Output a single integer denoting the maximum number of plants that can be picked without violating the non-adjacency condition.

## sample

3 3
P.P
.P.
P.P

4