Problem L
Window Shopping

One optimal way of installing windows for the first sample case. The blue cells are the shops. The red edges are the windows.

You are to choose some of the empty cells to build shops. All remaining empty cells, plus the two escalator cells, are walkable by the customers. If an empty cell is reachable from both escalators via some walkable cells, it becomes a hallway. A shop window can be installed on an edge between a shop and a hallway.

After the floor planning, it is allowed to have some empty cells not reachable from both escalators. These empty cells are thus not hallways and cannot have windows installed around them. Also, an escalator is not a hallway and windows cannot be installed on any side of an escalator.

Based on the latest customer analysis report, the profit of the shopping mall grows proportionally to the number of windows inside the mall. You need to therefore determine the maximum number of shop windows that can be installed in the shopping mall.

Input

The first line of input contains two positive integers $r$ and $c$ ($4 \leq r \cdot c \leq 99$), which are the size of the shopping mall. The mall is a grid with $r$ rows and $c$ columns of cells.

Each of the next $r$ lines contains a string of length $c$. Each character in the string is one of:

• a dot ‘.’ representing an empty cell

• a hash ‘#’ representing a pillar

• a letter ‘U’ representing an Up escalator (Exactly one of these will appear)

• a letter ‘D’ representing a Down escalator (Exactly one of these will appear)

It is guaranteed that initially all empty cells are reachable from both escalators.

Output

Output a single integer, which is the maximum number of windows the shopping mall can accommodate.

4 5
.....
#U...
...#.
...D.

13

4 4
..#U
..#D
..#.
....

5

3 2
##
.D
U.

0