Задано ігрове поле розмірами n × m, деякі клітинки якого вже замощено. Замостити вільні сусідні клітинки поля доміношкою розмірами 1 × 2 коштує a умовних одиниць. Замостити вільну клітинку поля квадратиком розмірами 1 × 1 коштує b умовних одиниць.

Визначіть, яка мінімальна сума грошей потрібна, щоб дозамостити усе поле.

Формат вхідних даних

Перший рядок містить чотири числа n, m, a, b (1 ≤ n, m ≤ 100, a, b - цілі числа, які по модулю не перевищують 1000). Кожен з наступних n рядків містить по m символів: символ "." (точка) позначає заняту клітинку поля, а символ "*" (зірочка) - вільну.

Формат вихідних даних

Виведіть мінімальну суму грошей, маючи яку можна замостити вільні клітинки поля (і лише їх).

Приклад вхідних даних

2 3 3 2
.**
.*.

Приклад вихідних даних

5