你需要帮助一家新建的购物中心设计其楼层布局。购物中心可以看作是一个矩形的网格。如果两个单元格共享一条边，则它们是相邻的。每个单元格可以是空地、柱子或自动扶梯。购物中心内恰好有两个自动扶梯：一个上行，一个下行。注意，自动扶梯所占空间很小，顾客可以自由穿过它们，而无需真正上下楼。

你需要选择一些空地来建造商店。所有剩余的空地以及两个自动扶梯所在的单元格，对顾客来说都是可通行的。如果一个空地可以通过某些可通行单元格从两个自动扶梯到达，那么它就成为一个走廊。商店橱窗可以安装在商店和走廊之间的公共边上。

在楼层规划完成后，允许存在一些无法从两个自动扶梯到达的空地。这些空地因此不是走廊，也不能在它们周围安装橱窗。此外，自动扶梯本身不是走廊，且自动扶梯的任何一侧都不能安装橱窗。

根据最新的客户分析报告，购物中心的利润与商场内橱窗的数量成正比。因此，你需要确定购物中心内最多可以安装多少个商店橱窗。

第一个样例的一种最优橱窗安装方案。蓝色单元格为商店，红色边为橱窗。

输入格式

输入的第一行包含两个正整数 $r$ 和 $c$ ($4 \le r \cdot c \le 99$)，表示购物中心的大小。商场是一个 $r$ 行 $c$ 列的网格。

接下来的 $r$ 行，每行包含一个长度为 $c$ 的字符串。字符串中的每个字符为以下之一： 点 ‘.’ 表示一个空地 井号 ‘#’ 表示一个柱子 字母 ‘U’ 表示一个上行自动扶梯（恰好出现一次） 字母 ‘D’ 表示一个下行自动扶梯（恰好出现一次）

保证初始时所有空地均可从两个自动扶梯到达。

输出格式

输出一个整数，表示购物中心最多可以容纳的橱窗数量。

样例

样例输入 1

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

样例输出 1

13

样例输入 2

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

样例输出 2

5

样例输入 3

3 2
##
.D
U.

样例输出 3

0