409681: GYM103678 D Бернард и кирпичная стена
Description
Бернард спрятался в кирпичном домике, но внезапно пришел большой серый волк и начал с неистовой силой дуть на домик. Подув примерно три минуты, волк устал и ушел. Но после этого в кирпичной стене домика образовалось множество дыр. Бернард хочет починить стену с минимальными затратами.
Стена представляет собой прямоугольное поле размера $$$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