Maximum Non-Adjacent Flower Placement

In this problem, you are given a grid of size (n \times m) where each cell is either empty (represented by '.') or contains a tree (represented by 'T'). Your task is to place as many flowers (denoted by 'F') in the empty cells as possible such that no two flowers are adjacent, not even diagonally. In other words, if a flower is placed in cell ((i, j)), then none of its eight neighboring cells (((i-1,j-1)), ((i-1,j)), ((i-1,j+1)), ((i,j-1)), ((i,j+1)), ((i+1,j-1)), ((i+1,j)), ((i+1,j+1))) can contain a flower.

Note that cells containing trees cannot hold a flower. The grid is provided in row-major order. Your solution should read from stdin and output the answer to stdout.

inputFormat

The first line contains two integers (n) and (m) separated by a space, indicating the number of rows and columns of the grid respectively. The following (n) lines each contain a string of length (m) consisting of the characters '.' or 'T'.

outputFormat

Output a single integer representing the maximum number of flowers that can be planted in the grid under the given constraints.## sample

4 4
....
.T.T
...T
T..T

4