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

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

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