Board

problem

Given the squares of $R * C$. Each square is either an empty square or a square with a hole. The given square meets the following conditions.

• The cells with holes are connected. (You can move a square with a hole in the cross direction to any square with a hole)
• Empty cells are connected.

You can generate rectangular tiles of any length with a width of $1$. I would like to install multiple tiles to fill all the holes in the square. When installing tiles, the following restrictions must be observed.

• Tiles can only be installed vertically or horizontally in the $2$ direction.
• Do not install more than one tile on one square.
• There should be no tiles on the squares without holes.

Please answer the minimum number of tiles when all the squares with holes are filled with tiles while observing the above restrictions.

output

Output the minimum number of times. Please also output a line break at the end.

Example

Input

5 5 ..... .#.#. .###. .#.#. .....

Output

3

inputFormat

outputFormat

output

Output the minimum number of times. Please also output a line break at the end.

Example

Input

5 5 ..... .#.#. .###. .#.#. .....

Output

3

样例

5 5
.....
.#.#.
.###.
.#.#.
.....

3