D. 海滩

时间限制： $1$ 秒
内存限制： $256$ MB

安德鲁热爱大海。因此，在盛夏时节，他决定去海滩，并带上一张日光浴床去晒太阳。

海滩是一个有 $n$ 行和 $m$ 列的矩形区域。海滩上的一些格子是空闲的，一些有道路、石头、商店和其他不可移动的物体。沿着边相邻的两个格子可以放置水平或竖直方向的日光浴床。

安德鲁希望把床放在某个地方，但运气不佳，可能已经没有空闲的地方了！因此，安德鲁请你帮他找一个放床的空闲位置。安德鲁的床也必须放在两个相邻的空闲格子上。

如果没有两个相邻的空闲格子，为了腾出放床的空间，你将不得不打扰其他游客。你可以执行以下操作：

• 走到某张日光浴床前，给它的主人造成 $p$ 单位的不适感后，抓住床的一边将其抬起并旋转 $90$ 度。床的一半必须保持在原来的格子，另一半必须移动到空闲的格子。同时，旋转过程中床经过的地方可以有任何东西。

  将日光浴床绕格子 $(1,2)$ 旋转 $90$ 度。

• 走到某张日光浴床前，给它的主人造成 $q$ 单位的不适感后，将床沿其长边平移一个格子。床的一半必须移动到另一半原来占据的格子，而另一半则移动到空闲的格子。

  将日光浴床向右平移一个格子。

在任何时刻，每张日光浴床都占据两个相邻的空闲格子。你一次只能移动一张日光浴床。

帮助安德鲁腾出一个放置日光浴床的空间，使得给其他游客造成的不适感单位总数尽可能最小，或者判断这是不可能的。

输入

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 300\,000$，$1 \le n \cdot m \le 300\,000$）——矩形的行数和列数。

第二行包含两个整数 $p$ 和 $q$（$1 \le p, q \le 10^9$）——分别表示旋转和移动一张日光浴床造成的不适感单位数。

接下来的 $n$ 行每行包含 $m$ 个字符，描述矩形的格子。每行由字符 "L"、"R"、"D"、"U"、"." 和 "#" 组成，表示格子的类型。字符 "L"、"R"、"D" 和 "U" 分别表示放在该格子的日光浴床的一半——左、右、下、上半部分。字符 "." 表示一个空闲格子，字符 "#" 表示被某个不可移动物体占据的格子。

输出

输出一个整数——为腾出一个放日光浴床的空间而给其他游客造成的最小可能不适感单位总数。如果不可能腾出空间，则输出 $-1$。

样例

输入

2 5
5 2
.LR##
##LR.

输出

4

输入

2 3
4 5
LR.
#.#

输出

-1

输入

4 3
10 10
.LR
###
UU#
DD.

输出

-1

输入

3 6
10 7
.U##.#
#DLR##
.##LR.

输出

24

提示

在第一个样例中，我们可以将上面的床向左移动，将下面的床向右移动。安德鲁将能够在海滩中间竖直放置他的床。我们将造成 $2+2=4$ 单位的不适感。可以容易地证明这是最优答案。

第一个样例中的最优策略（安德鲁的床被染成白色）。

在第二个样例中，不可能为安德鲁的床腾出空间。问题陈述中展示了海滩经过任意旋转和移动后所有可能的状态。