Problem Description

There is a grid consisting of $ r $ rows and $ c $ columns, with a total of $ r×c $ squares. Each square is marked with either * or .. Let $ C_{i,j} $ denote the character written on the square in the $ i $-th row and $ j $-th column.

Kenkoooo decided to place SoundHound advertisements on the squares marked with .. Each square can only have one advertisement. However, placing advertisements on two adjacent squares would be counterproductive. Here, adjacent squares refer to squares that are directly adjacent vertically or horizontally.

How many advertisements can Kenkoooo place at most?

Input Format

The input is given from the standard input in the following format:

$ r $ $ c $ $ C_{1,1} $$ C_{1,2} $ $ ... $ $ C_{1,c} $ $ : $ $ C_{r,1} $$ C_{r,2} $ $ ... $ $ C_{r,c} $

Output Format

Output the maximum number of advertisements Kenkoooo can place.

Sample Input and Output

Sample Input #1

3 3
...
...
...

Sample Output #1

5

Sample Input #2

2 2
**
**

Sample Output #2

0

Sample Input #3

1 1
.

Sample Output #3

1

Sample Input #4

3 4
*..*
..**
*...

Sample Output #4

4

Notes/Hints

Constraints

• $1≦r,\ c≦40$
• $ C_{i,j} $ consists of either . or *

Sample Explanation 1

If we denote the squares with advertisements by #, we can place 5 advertisements as follows:

#.#
.#.
#.#

Sample Explanation 2

Unfortunately, there are cases where no advertisements can be placed.

见题面 Input 部分

见题面 Output 部分