Description

In 2016, Sister Jiayuan fell in love with a game called BnB.

Simply put, in this game you place several bombs on a map to see whether you can hit the opponent or avoid the opponent’s bombs. While playing, Little H thought of this question: given a map, what is the maximum number of bombs you can place so that no two bombs can hit each other? A bomb’s explosion reaches the entire row and column where it is placed. The explosion can pass through soft stones, but cannot pass through hard stones.

You are given an $n \times m$ grid map: the symbol * denotes an empty cell; the explosion can pass through it, and you can place a bomb on it. The symbol x denotes a soft stone; the explosion can pass through it, but you cannot place a bomb on it. The symbol # denotes a hard stone; the explosion cannot pass through it, and you cannot place a bomb on it. For example, given a $1 \times 4$ grid map *xx*, you can place at most one bomb on this map. Given another $1 \times 4$ grid map *x#*, you can place at most two bombs on this map.

Now, given any $n \times m$ grid map from Little H, determine the maximum number of bombs that can be placed.

Input Format

The first line contains two positive integers $n, m$, where $n$ is the number of rows and $m$ is the number of columns.

Then $n$ lines follow, each containing $m$ characters representing the grid map. The number of * does not exceed $n \times m$.

Output Format

Output a single integer $a$, the maximum number of bombs that can be placed.

4 4
#***
*#**
**#*
xxx#

5

Hint

$1 \leq n, m \leq 50$.

Translated by ChatGPT 5