Zədələnmiş parket#2086
Otağın ölçüləri M \times N olan bir otağın döşəməsi parketlə döşənib. Bəzi parket plitələr zədələnib. Petro otağı təmir etmək və yalnız zədələnmiş plitələri dəyişmək istəyir. Mağazada iki növ parket plitəsi tapır: 1 \times 2 ölçülü plitələr, hər biri rubl (Petro başa düşür ki, 1 \times 2 plitələri dərəcə fırladılaraq 2 \times 1 plitəyə çevrilə bilər) və hər biri rubl olan 1 \times 1 ölçülü plitələr. Petro 1 \times 2 plitəsini iki 1 \times 1 plitəyə bölə bilməz.
Petronun təmir üçün sərf etməli olduğu minimum məbləği müəyyən edin.
Girişin birinci sətrində ədəd var: , , , (1 \leq N, M \leq 300, -nin modulu -dən çox deyil). Sonra gələn sətrin hər birində simvol var: "." (nöqtə) qüsursuz plitəni, "*" (ulduz) isə zədələnmiş plitəni göstərir. Sətirlərin sonunda boşluq ola bilər. Fayl boş sətirərlə bitə bilər.
Yalnız cavabı — zədələnmiş parket plitələrinin (və yalnız onların) dəyişdirilməsi üçün lazım olan minimum məbləği çap edin.
Nümunə 1