D. Пляж
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Андрей обожает море. Именно поэтому в разгар летнего сезона он решил отправиться на пляж, взяв с собой лежак, чтобы позагорать.

Пляж представляет собой прямоугольное поле, состоящее из $$$n$$$ строк и $$$m$$$ столбцов. Некоторые клетки этого поля свободны, на некоторых расположены дорожки, камни, ларьки и другие несдвигаемые объекты, а так же на двух соседних по стороне клетках могут стоять лежаки, расположенные как горизонтально, так и вертикально.

Андрей надеется поставить где-то свой лежак, но вот незадача, свободных мест для него может уже не быть! Именно поэтому Андрей просит вас помочь найти ему свободное место для лежака. Лежак Андрея тоже должен занимать две соседние по стороне клетки.

Если двух соседних свободных клеток нет, то для того, чтобы освободить место для лежака, придется потревожить других туристов. Для этого вы можете делать следующие действия:

  • Подойти к любому лежаку, и доставив $$$p$$$ единиц дискомфорта его хозяину, поднять лежак за одну из сторон и повернуть на $$$90$$$ градусов. Одна из половин лежака должна остаться в той же клетке, а вторая переместиться в свободную клетку. При этом во время поворота на пути лежака может быть что угодно.
    Поворот лежака на $$$90$$$ градусов вокруг клетки $$$(1, 2)$$$.
  • Подойти к любому лежаку, и доставив $$$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$$$ единицы дискомфорта. Можно показать, что доставить меньшее количество дискомфорта не получится.

Оптимальные действия в первом примере (лежак Андрея обозначен белым цветом).
Во втором примере из условия невозможно освободить место для лежака Андрея. Всевозможные состояния пляжа после поворотов и сдвигов показаны в условии задачи.