Задача №3910. Замощение доминошками
Дано игровое поле размера \(n \times m\), некоторые клетки которого уже покрыты. Макс можем замостить две свободные соседние клетки поля доминошкой размера \(1 \times 2\), и это стоит ей \(a\) условных единиц, а замостить свободную клетку поля квадратитом размера \(1 \times 1\) — \(b\) условных единиц. Определите, какое минимальное количество условных единиц требуется для того, чтобы замостить все поле.
Формат входных данных
В первой строке входных данных содержится 4 целых числа \(n\), \(m\), \(a\) и \(b\) (\(1 \le n, m \le 100\), \(|a| \le 1000\), \(|b| \le 1000\)). Каждая из последующих \(n\) строк содержит \(m\) символов "." и "*". При этом, звездочка обозначает свободную клетку поля, а точка — занятую.
Формат выходных данных
В выходной файл выведите одно число — искомую минимальную стоимость.
2 3 3 2 .** .*.
5