Дано игровое поле размерами , некоторые клетки которого уже замощены. Замостить свободные соседние клетки поля доминошкой размерами стоит условных единиц. Замостить свободную клетку поля квадратиком размерами стоит условных единиц.
Определите, какая минимальная сумма денег нужна, чтобы дозамостить всё поле.
Первая строка содержит четыре числа — целые числа, по модулю не превосходящие . Каждая из последующих строк содержит по символов: символ "." (точка) обозначает занятую клетку поля, а символ "*" (звёздочка) — свободную.
Выведите минимальную сумму денег, имея которую можно замостить свободные клетки поля (и только их).