Kaguya is trying to plan out a shopping trip with Kei Shirogane. As a result, she will build Kei a mall!

The mall takes the form of an ~R \times C~ grid with an up escalator and a down escalator, as the mall is not on ground level. The mall has some pillars in it where construction cannot occur, but all empty squares are reachable from both escalators right now if movement is allowed between grid squares that share an edge.

Kaguya will build shops in some empty cells. Cells that are empty or contain escalators are walkable. An empty cell is a hallway if it is reachable from both escalators via walkable cells. A shop directly adjacent to a hallway can install a window facing the hallway.

Kaguya wants to maximize the number of windows that the mall builds to maximize the amount of window shopping she does with Kei. Compute this number.

Constraints

~4 \le R \cdot C \le 99~

In tests worth 1 mark, ~\min(R, C) \le 1~.

In tests worth an additional 2 marks, ~\min(R, C) \le 2~.

In tests worth an additional 2 marks, ~\min(R, C) \le 3~.

In tests worth an additional 2 marks, ~\min(R, C) \le 4~.

In tests worth an additional 2 marks, ~\min(R, C) \le 5~.

In tests worth an additional 2 marks, ~\min(R, C) \le 6~.

Input Specification

The first line contains two integers ~R~ and ~C~.

Each of the next ~R~ lines contains a string of ~C~ characters. Each character is one of .#UD, indicating an empty cell, pillar, up escalator, and down escalator, respectively.

Output Specification

Output the maximum number of windows that can be made in the mall.

Sample Input 1

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

Sample Output 1

13

Sample Input 2

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

Sample Output 2

5

Sample Input 3

3 2
##
.D
U.

Sample Output 3

0