Задачи
Замощение доминошками
Замощение доминошками
Дано игровое поле размерами $n \times m$, некоторые клетки которого уже замощены. Замостить свободные соседние клетки поля доминошкой размерами $1 \times 2$ стоит $a$ условных единиц. Замостить свободную клетку поля квадратиком размерами $1 \times 1$ стоит $b$ условных единиц.
Определите, какая минимальная сумма денег нужна, чтобы дозамостить всё поле.
\InputFile
Первая строка содержит четыре числа $n, m, a, b~(1 \le n, m \le 100, a, b$ --- целые числа, по модулю не превосходящие $1000)$. Каждая из последующих $n$ строк содержит по $m$ символов: символ "\textbf{.}" (точка) обозначает занятую клетку поля, а символ "\textbf{*}" (звёздочка) --- свободную.
\OutputFile
Выведите минимальную сумму денег, имея которую можно замостить свободные клетки поля (и только их).
Входные данные #1
2 3 3 2 .** .*.
Выходные данные #1
5
Входные данные #2
3 4 5 3 *..* **** ***.
Выходные данные #2
23