Youngkwail Club Room

Time limit1sMemory limit256 MB

Summary

Cover all '.' cells of a grid with 1x1 and 1x2 tiles, avoiding 'X' pillars, using the fewest tiles possible.

Level: Hard9 of 10
Topics: Graph, DFS, Union-find, Combinatorics
Solved: No attempts yet

Problem

Youngkwail was about to lose its club room, but the skill of its outstanding members was recognized and the club room was reassigned. Now happy, Youngkwail's treasurer Jaehyun buys $1 \times 2$ tiles and $1 \times 1$ tiles and wants to cover the entire club room floor.

Given a floor plan of the club room, write a program that prints the minimum number of tiles needed to cover the entire floor, so Jaehyun can save money.

Input

The first line gives the number of rows $N$ and columns $M$ of the floor plan. ( $1 \le N \le 50$ , $1 \le M \le 50$ )

Starting from the second line, $N$ lines each give a string of length $M$ describing the floor plan. In the $i+1$ -th line, the $j$ -th character is . for floor and X for a pillar.

Output

Print the minimum number of tiles needed on the first line.

Examples1

Example 1
Input
```
3 4
.X..
...X
...X
```
Expected output
```
5
```