Задачи
Замощение доминошками
Замощение доминошками
Дано игровое поле размерами 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