Gallery

A gallery map is an M×N grid of square cells. Each cell is either a wall (X) or empty space (.). You may think of walls as gray cells and empty spaces as white cells.

Pictures will be hung on the walls. Each picture is twice as long as one side of a grid cell. A picture may be hung only on a wall face that borders empty space, and pictures on the same wall face must not overlap. Given the gallery map, compute the maximum number of pictures that can be hung.

The first line contains the gallery's vertical length M and horizontal length N. (1 ≤ M, N ≤ 1,000) The next M lines each contain a string of length N. Each character is either X or ., where X represents a wall and . represents empty space.

In every input, the first and last rows and the first and last columns are all walls.

Output the maximum number of pictures that can be hung.