CF1753D.The Beach

Andrew loves the sea. That's why, at the height of the summer season, he decided to go to the beach, taking a sunbed with him to sunbathe.

The beach is a rectangular field with $n$ rows and $m$ columns. Some cells of the beach are free, some have roads, stones, shops and other non-movable objects. Some of two adjacent along the side cells can have sunbeds located either horizontally or vertically.

Andrew hopes to put his sunbed somewhere, but that's a bad luck, there may no longer be free places for him! That's why Andrew asked you to help him to find a free place for his sunbed. Andrew's sunbed also should be places on two adjacent cells.

If there are no two adjacent free cells, then in order to free some place for a sunbed, you will have to disturb other tourists. You can do the following actions:

• Come to some sunbed and, after causing $p$ units of discomfort to its owner, lift the sunbed by one of its sides and rotate it by $90$ degrees. One half of the sunbed must remain in the same cell and another half of the sunbed must move to the free cell. At the same time, anything could be on the way of a sunbed during the rotation .

  

  

  

  Rotation of the sunbed by $90$ degrees around cell $(1, 2)$.

• Come to some sunbed and, after causing $q$ units of discomfort to its owner, shift the sunbed along its long side by one cell. One half of the sunbed must move to the place of another, and another — to the free cell.

  

  

  

  Shift of the sunbed by one cell to the right.

In any moment each sunbed occupies two adjacent free cells. You cannot move more than one sunbed at a time.

Help Andrew to free a space for his sunbed, causing the minimum possible number of units of discomfort to other tourists, or detect that it is impossible.

安德鲁热爱大海。因此，在夏季旅游旺季的高峰期，他决定带着一张日光浴床前往海滩晒太阳。

海滩是一个 $n$ 行 $m$ 列的矩形区域。海滩上的某些格子是空闲的，某些格子上则有道路、石头、商店及其他不可移动的障碍物。某些两个沿边相邻的格子上可能已放置了一张日光浴床，其方向为水平或垂直。

安德鲁希望在某处安置自己的日光浴床，但很不巧，可能已没有空闲位置供他使用！因此，安德鲁请你帮他找到一个可放置日光浴床的空闲位置。安德鲁的日光浴床也必须占据两个相邻的格子。

如果不存在两个相邻的空闲格子，则为了腾出一张日光浴床的位置，你将不得不打扰其他游客。你可以执行以下操作之一：

• 走到某张日光浴床旁，将其一侧抬起并绕该侧所在格子旋转 $90^\circ$，从而造成其主人 $p$ 单位的不适。旋转后，日光浴床的一半仍留在原格子中，另一半则移入一个空闲格子；旋转过程中，日光浴床的路径上可以存在任意物体（即路径无障碍要求）。

  

  

  

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

• 走到某张日光浴床旁，沿其长边方向将其整体平移一格，从而造成其主人 $q$ 单位的不适。平移时，日光浴床的一半移至另一半原先所在的格子，另一半则移入一个空闲格子。

  

  

  

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

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

请帮助安德鲁腾出一张日光浴床的位置，使对其他游客造成的总不适单位数最小；若无法实现，请判断并报告该情况。

The first line contains two integers $n$ and $m$ ($1 \le n, m \le 300\,000$, $1 \le n \cdot m \le 300\,000$) — the number of rows and columns in rectangle.

The second line contains two integers $p$ and $q$ ($1 \le p, q \le 10^9$) — the number of units of discomfort caused by rotation and shift of a sunbed, respectively.

Each of the following $n$ lines contains $m$ characters, describing cells of the rectangle. Each lines consists of characters "L", "R", "D", "U", "." and "#", denoting the type of the cell. Characters "L", "R", "D" and "U" denote a half of a sunbed placed in the cell — left, right, bottom and top half, respectively. Character "." denotes a free cell and character "#" — a cell, occupied by some non-movable object.

第一行包含两个整数 $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" 分别表示该单元格中放置了一张日光浴床的左半部分、右半部分、下半部分和上半部分；"." 表示空闲单元格；"#" 表示被某个不可移动物体占据的单元格。

Print one integer — the minimum possible number of units of discomfort, caused to other tourists, to free a space for a sunbed. If it is impossible to free a space for a sunbed, print $-1$.

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

In the first example we can shift upper sunbed to the left and lower sunbed — to the right. Andrew will be able to put his sunbed vertically in the middle of the beach. We well cause $2 + 2 = 4$ units of discomfort. It is easy to prove that it is an optimal answer.

Optimal strategy in the first example (Andrew's sunbed is colored white).

In the second example it is impossible to free a space for Andrew's sunbed. All possible states of the beach after any rotates and shifts are illustrated in the problem statement.

在第一个例子中，我们可以将上方的躺椅向左移动，下方的躺椅向右移动。安德鲁便可在海滩正中央竖直放置他的躺椅。这将造成 $2 + 2 = 4$ 单位的不适度。容易证明这是最优解。

第一个例子中的最优策略（安德鲁的躺椅以白色标出）。

在第二个例子中，无法为安德鲁的躺椅腾出空间。问题描述中已展示了所有可能的海滩状态（经过任意旋转与平移后）。