409681: GYM103678 D Бернард и кирпичная стена

D. Бернард и кирпичная стенаограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Бернард спрятался в кирпичном домике, но внезапно пришел большой серый волк и начал с неистовой силой дуть на домик. Подув примерно три минуты, волк устал и ушел. Но после этого в кирпичной стене домика образовалось множество дыр. Бернард хочет починить стену с минимальными затратами.

Стена представляет собой прямоугольное поле размера $$$N$$$ на $$$M$$$ клеток, где клетки, занятые кирпичами, представлены символами «*», а дыры в стене представлены символами «.». Бернард может класть кирпичи только горизонтально. При этом кирпич занимает две соседние пустые клетки. Также Бернард может класть половинку кирпича, она занимает только одну клетку. Целый кирпич стоит $$$A$$$ монет, половинка стоит $$$B$$$ монет. Бернард хочет заполнить все пустые клетки кирпичами и при этом потратить минимальное количество денег.

Помогите ему произвести требуемые расчеты.

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

Первая строка входных данных содержит четыре целых числа $$$N$$$, $$$M$$$, $$$A$$$, $$$B$$$ $$$(1 \le N, M, A, B \le 1000)$$$ — размеры стены, цена целого кирпича и цена половинки кирпича соответственно.

Далее идут $$$N$$$ строк длины $$$M$$$, состоящие из символов «*» или «.» — описание стены.

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

Выведите единственное целое число — минимальную стоимость починки стены.

Система оценки

Группа	Доп. ограничения	Баллы	Требуемые подзадачи	Тип проверки
$$$1$$$	$$$2 \cdot B \le A$$$	$$$50$$$	—	Полная
$$$2$$$	—	$$$50$$$	$$$1$$$	Полная

ПримерыВходные данные

4 5 3 2
**.**
*....
*...*
****.

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

15

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

3 3 5 2
*.*
...
..*

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

12