eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Замощение доминошками

Замощение доминошками

Лимит времени 1 секунда
Лимит использования памяти 128 MiB

Дано игровое поле размерами n \times m, некоторые клетки которого уже замощены. Замостить свободные соседние клетки поля доминошкой размерами 1 \times 2 стоит a условных единиц. Замостить свободную клетку поля квадратиком размерами 1 \times 1 стоит b условных единиц.

Определите, какая минимальная сумма денег нужна, чтобы дозамостить всё поле.

Входные данные

Первая строка содержит четыре числа n, m, a, b~(1 \le n, m \le 100, a, b — целые числа, по модулю не превосходящие 1000). Каждая из последующих n строк содержит по m символов: символ "." (точка) обозначает занятую клетку поля, а символ "*" (звёздочка) — свободную.

Выходные данные

Выведите минимальную сумму денег, имея которую можно замостить свободные клетки поля (и только их).

Пример

Входные данные #1
2 3 3 2
.**
.*.
Выходные данные #1
5
Входные данные #2
3 4 5 3
*..*
****
***.
Выходные данные #2
23