The Beach
Contest: Codeforces Round 829 (Div. 1)
Difficulty rating: 2400
Tags: constructive algorithms, dfs and similar, graphs, shortest paths

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.

Input format:
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.

Output format:
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$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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).

Example input:
2 5
5 2
.LR##
##LR.

Example output:
4

Example input:
2 3
4 5
LR.
#.#

Example output:
-1

Editorial:
Let's paint our field in a chess coloring.
Now let's consider our operations not as the movement of sunbeds, but as the movement of free cells. Then, a free cell adjacent to the long side of the sunbed can move to a cell of the sunbed that is not adjacent to this one, for $$$p$$$ units of discomfort. A free cell adjacent to the short side of the sunbed can move to a cell of the sunbed that is not adjacent to this one, for $$$q$$$ units of discomfort. Note that in this cases, the free cell does not change its color (in chess coloring).
Since each sunbed should occupy one black and one white cell, then some two free cells of different colors should move to neighboring ones using operations.
It can be shown that in the optimal answer we use no more than one operation with each sunbed.
Then, for each position, looking at the adjacent sunbeds, we will determine where the free cell can move if it turns out to be in this position. Let's construct a weighted oriented graph on the cells of the field. Edge $$$(x_1, y_1) \rightarrow (x_2, y_2)$$$ of weight $$$w$$$ (equal to $$$p$$$ or $$$q$$$) will mean that there is a sunbed such that by moving it with an operation that brings $$$w$$$ discomfort, we will free the cell $$$(x_2, y_2)$$$ and block the cell $$$(x_1, y_1)$$$.
Note that the graphs on the black and white cells are not connected. Let's run Dijkstra's algorithm from all free cells at once. Then, for each cell $$$d_{x, y}$$$ - the minimum distance in this graph from a free cell is equal to the minimum amount of discomfort that must be used to free this cell.
The answer to the problem is the minimum for all pairs $$$(x_1, y_1)$$$, $$$(x_2, y_2)$$$ neighboring cells, $$$d_{x_1, y_1} + d_{x_2, y_2}$$$. Or $$$-1$$$ if there is no pair of adjacent cells, both of which are reachable from the free ones.
Asymptotics of the solution: $$$\mathcal{O}(n m \cdot\log{(nm))}$$$