Maximum Bomb Placement

In 2016, Jieyuan fell in love with a game called Bomber Town. In this game, bombs are placed on a grid map, and their explosion affects every cell in the same row and column, unless blocked by a hard stone. More precisely, when a bomb explodes, its effect travels horizontally and vertically through any cell except that its propagation is stopped by a hard stone. Soft stones, however, do not block the explosion; they are penetrable by the blast, but bombs cannot be placed on them.

You are given an n × m grid map. Each cell of this map contains one of the following characters:

• *: an empty cell, where a bomb can be placed and where explosions pass through.
• x: a soft stone, where a bomb cannot be placed, but explosions still pass through.
• #: a hard stone, where a bomb cannot be placed and which also blocks bomb explosions.

A bomb in a particular cell will affect every cell in its row and column, but its effect stops once a # is encountered. Two bombs are said to "conflict" if one bomb lies in the explosion range of the other. Your task is to determine the maximum number of bombs that can be placed on the grid (only on * cells) so that no two bombs conflict with each other.

The segments for bomb explosion are defined by uninterrupted sequences of cells (cells which are not #) in the same row or column. Two bombs placed in the same segment will hit each other. Thus, the problem can be modeled by considering each continuous segment (in rows and columns) as nodes in a bipartite graph and placing a bomb corresponds to matching a row segment with a column segment (if the corresponding cell contains *).

Find the maximum matching in this bipartite graph, which equals the maximum number of bombs that can be placed on the grid.

Note on notation: Any mathematical formula must be rendered in LaTeX. For example, the grid dimensions can be represented as \( n \times m \).

inputFormat

The first line contains two integers \( n \) and \( m \) (the number of rows and columns, respectively). The next \( n \) lines each contain a string of length \( m \) representing the grid. The grid consists only of the characters *, x, and #.

outputFormat

Output a single integer, the maximum number of bombs that can be placed on the grid without any two bombs being in each other’s blast range.

sample

1 4
*xx*

1