Испорченный паркет#2086
Пол комнаты размером M \times N покрыт паркетными плитками. Некоторые плитки повреждены. Петро хочет отремонтировать комнату, заменив только повреждённые плитки. В магазине он находит два типа паркетных плиток: плитки размером 1 \times 2, каждая из которых стоит рублей (Петро знает, что плитки 1 \times 2 можно повернуть на градусов, чтобы они стали плитками 2 \times 1), и плитки 1 \times 1, каждая из которых стоит рублей. Петро не может разрезать плитку размером 1 \times 2 на две плитки размером 1 \times 1.
Определите минимальную сумму денег, которую Петро должен потратить на ремонт.
В первой строке входных данных содержатся числа: , , , (1 \leq N, M \leq 300, — целые числа, по модулю не превышающие ). Каждая из следующих строк содержит символов: "." (точка) обозначает неповреждённую плитку, "*" (звёздочка) — повреждённую плитку. В строках могут быть завершающие пробелы. Файл может оканчиваться пустыми строками.
Выведите одно число — минимальную стоимость замены повреждённых паркетных плиток (и только их).
Example 1