Planting Trees on a Grid

You are given an \(n \times m\) grid, where each cell is either empty (denoted by .) or blocked by an obstacle (denoted by #).

Your task is to plant as many trees as possible in the grid with the following conditions:

• No two trees can be planted in the same row.
• No two trees can be planted in the same column.
• A tree cannot be planted on a cell with an obstacle.

Determine the maximum number of trees that can be planted.

Note: If there is a cell available for planting (i.e. it contains a .) and its column has not been used yet, you may plant a tree there. The greedy strategy of checking row by row yields an optimal solution for the given constraints.

inputFormat

The input is read from stdin and has the following format:

1. The first line contains two integers \(n\) and \(m\) representing the number of rows and columns respectively.
2. The following \(n\) lines each contain a string of length \(m\) representing the grid. Each character is either . (an empty cell) or # (an obstacle).

outputFormat

Output to stdout a single integer — the maximum number of trees that can be planted under the given conditions.

4 4
....
.#..
..#.
....

4