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

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

Нужно замостить все свободные клетки (и только их) как можно дешевле.

В первой строке четыре целых числа $n$, $m$, $a$, $b$ ($1 \le n, m \le 100$, $|a| \le 1000$, $|b| \le 1000$).

В следующих $n$ строках по $m$ символов: . — занятая клетка, * — свободная.

Выведите минимальную сумму, за которую можно замостить все свободные клетки.