Harry Potter and Voldemort's Nose

Interview

Time limit2sMemory limit1024 MB

Summary

Count the pairs of horizontally or vertically adjacent free cells in an n by m grid, where each pair can hold the nose.

Level: Easy2 of 10
Topics: Implementation, Matrix
Solved: No attempts yet

Statement

At Hogwarts, back when Lord Voldemort was still called Tom Marvolo Riddle, he was a fairly attractive young man. Numerous dark deeds ruined his appearance: they cost him his nose.

Modern plastic surgery can fix this. He signed up for an operation to build an artificial nose, and the only remaining question is where to place it. He approached that question mathematically.

Voldemort's face is simplified to a grid rectangle with $n$ rows and $m$ columns. His new nose occupies exactly two cells that share a horizontal or vertical side. His eyes and mouth already occupy some cells, and the nose cannot overlap them. He wants to know how many ways he can place the nose on his face.

Input

The first line contains two integers $n$ and $m$ ( $1 \le n, m \le 1000$ ), the dimensions of Voldemort's face. Each of the next $n$ lines contains $m$ characters describing the face. The character # marks a cell that is already occupied, and the character . marks a free cell that may become one of the two cells of the nose.

Output

Print one integer, the number of ways to place the nose on the face.

Examples3

Example 1
Input
```
2 3
...
...
```
Expected output
```
7
```
Example 2
Input
```
3 4
..#.
#..#
..#.
```
Expected output
```
5
```

Example 3

Input

5 8
........
.##..##.
........
#......#
.######.

Expected output