Seat Relocation Optimization

You are given a seating arrangement in an office represented by a grid with R rows and C columns. Each cell in the grid is either occupied by an employee (E) or is empty (.). An employee is considered comfortable if at least one horizontally or vertically adjacent cell is empty. Otherwise, the employee must be relocated.

Your task is to compute the minimum number of relocations required so that every employee has at least one adjacent empty desk.

Note: Two cells are adjacent if they share a common side. In mathematical notation, if a cell is located at (i, j), its four potential neighbors are at (i-1, j), (i+1, j), (i, j-1), and (i, j+1).

The condition for an employee at cell (i, j) can be written in LaTeX as:

\[ \exists \ (dx,dy) \in \{(-1,0), (1,0), (0,-1), (0,1)\} \text{ such that } 0 \leq i+dx < R \text{ and } 0 \leq j+dy < C \text{ and } grid[i+dx][j+dy]='.' \]

If the above condition fails for an employee, then that employee must be relocated.

inputFormat

The first line contains two integers R and C indicating the number of rows and columns in the grid, respectively.

The next R lines each contain a string of length C consisting only of the characters E and ., representing the grid.

outputFormat

Output a single integer — the minimum number of relocations needed so that every employee has at least one empty adjacent desk.

## sample

3 3
EEE
E.E
EEE

4