Handshakes in a Grid

You are given an R × S grid. Each cell is either occupied by a person (represented by 'P') or empty (represented by '.'). Each person will shake hands with every person sitting in one of the eight neighboring cells (if present; note that a handshake between two persons is counted only once).

Mirko is the last to arrive. He follows these rules when taking his seat:

• If there is any empty cell, he will choose an empty cell where the number of persons in the adjacent eight cells is maximized.
• If there is no empty cell, he leaves without taking a seat.

After Mirko acts accordingly, calculate the total number of handshake events among all persons. (Each handshake between two persons should be counted exactly once.)

Formally, if a cell (i, j) is occupied, and any of the four directions among right, down, down-right, and down-left has an occupied cell, count that handshake, ensuring every handshake pair is counted only once.

The adjacent cells are defined by the eight directions: up, down, left, right, and the four diagonals. In addition, note that a handshake only happens if both cells are occupied.

The formula for counting handshake pairs can be expressed in LaTeX as:

$$ H = \sum_{(i,j) \in \text{occupied}} \Bigl(1_{(i,j+1) \in \text{occupied}} + 1_{(i+1,j) \in \text{occupied}} + 1_{(i+1,j+1) \in \text{occupied}} + 1_{(i+1,j-1) \in \text{occupied}}\Bigr) $$

inputFormat

The first line contains two integers R and S (the number of rows and columns, respectively).

Each of the next R lines contains a string of length S consisting of characters 'P' (denoting a person) and '.' (denoting an empty cell).

outputFormat

Output a single integer: the total number of handshake events that occur after Mirko has either taken his optimal seat or left if no empty seat was available.

sample

3 3
P.P
.P.
P.P

7