403728: GYM101246 C Explode 'Em All

The prime minister of Berland decided to build a new city in the country. It's hard to describe the excitement of all Berland citizens, but indeed this is great news from the economic, social and cultural standpoints.

The land in Berland is occupied almost entirely and it's very hard to find free space for construction, so it was decided to build the city on a stony terrain. The map of this terrain is represented as an n × m grid, where each cell of the grid is either an empty space or a rock.

Of course, before construction is started, the given terrain must be completely cleared from rocks. As you may guess, you were hired to complete this mission. Your goal is to destroy all rocks by dropping bombs from a plane. A bomb can be dropped on any cell of the map, and you are free to select where you want to drop each bomb. When a bomb targeted for cell (i, j) reaches the ground, it destroys all rocks in row i and also all rocks in column j of the grid. If cell (i, j) contains a rock, this rock is also destroyed.

Please help the prime minister of Berland to find the minimum number of bombs required to completely clear the given terrain from rocks.

The first line of input contains two integers n and m (1 ≤ n, m ≤ 25) — the number of rows and columns correspondingly. Each of the next n lines contains m characters describing the terrain. An empty space is denoted by ".", while a rock is denoted by "*".

Write a single integer to the output — the minimum numbers of bombs required for destroying all rocks on the terrain.

8 10
..........
..***..*.*
.*.......*
.*.......*
.*.......*
.....*****
..........
.........*

2

3 4
....
....
....

0

In the first sample test it's only required to drop 2 bombs from a plane: one bomb to cell (2,2) and another bomb to cell (6, 10). Row and column indices in this explanation are 1-based.