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