Emergency weather report! In the town of Rainyville, a torrential downpour has begun to flood the town!

One particular structure within the town begins to collect water in its enclosures. From the side, the view can be described as a grid of ~R~ rows and ~C~ columns. Each grid cell can have a block (a part of the structure), indicated in the diagram below with a black cell, or is free for water to flow in. The structure of blocked cells will always be connected, and so every block shares a side with at least one other block. A non-block cell can either contain water or be empty, indicated with blue to indicate it is full of water or white to indicate it's empty.

Water behaves in a very particular way with this representation:

• If a cell contains water, the left and right non-block cells will also have water
• If water can flow to the leftmost or rightmost cells, then it flows out of the structure and the cell remains empty
• Gravity pulls water downward, and all water initially falls down from the topmost row as rain
• In one connected body of water, the water level (maximum row of any cell) must remain the same throughout
• In order for a cell to contain water, it must be in the same connected body of water as a cell that can be rained on (no blocks above it)

Rain water will continue to pour down until the structure is filled with the maximum amount of water. Consider the following example:

In this case, ~31~ cells of water can be filled into this structure. Notice that at the ~3^{\text{rd}}~ row from the bottom and ~14^{\text{the}}~ column from the left, the cell is filled with water. This is because all water cells in a connected body must be levelled.

Also notice that the cells at row ~5~ from column ~5~ to ~7~ inclusive, there is no water. This is because if there were, it would mean there must be at least one cell of water in the body of water that has no block above it so that it can collect rain water, which is not possible.

Additionally, at row ~6~ column ~3~, it is empty. This is because water flows out of the cell at row ~6~ and column ~1~, and because all water must be levelled, neither row ~6~ column ~2~ nor row ~6~ column ~3~ could have had water.

Input Specification

The first line contains two spaced integers, ~R~ and ~C~ ~(1 \le R,C \le 10^3)~, denoting the number of rows and columns of the grid.

The next ~R~ lines contains a string of ~C~ characters, each character either being a . to denote an unoccupied cell, and # denoting a block cell.

The last row will always be all block cells.

Output Specification

On a single line, output the maximum number of cells of water the structure can store after sufficient rain water has fallen.

Subtasks

Subtask	Description	Percentage of Marks
~1~	The blocks form vertical pillars. Each block cell above the bottom row will be directly above another block cell.	~50~
~2~	No additional constraints	~50~

Sample Input 1

8 17
.................
.................
...#####.........
#..#...#.........
#..#####....###..
#....#....#.#.#.#
#....#....#.#...#
#################

Output for Sample Input 1

31

Explanation of Output for Sample Input 1

This sample case corresponds to the example as described in the problem statement.

Sample Input 2

7 8
........
.#####..
.#...#..
.#.#.#.#
##.###.#
##.....#
########

Output for Sample Input 2

9

Explanation of Output for Sample Input 2

The water that can be collected is shown below. Remember that all water in a connected body must remain levelled, and that all cells with water must be in the same body of water as another cell that can be rained on (no blocks above).