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

Дано игровое поле размерами $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$ символов: символ "." (точка) обозначает занятую клетку поля, а символ "*" (звёздочка) — свободную.

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

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

Примеры