Зіпсований паркет#2086
Підлога в кімнаті розміром M \times N вкрита паркетними плитками. Деякі з плиток пошкоджені. Петро хоче відремонтувати кімнату, замінивши лише пошкоджені плитки. У магазині він знаходить два типи паркетних плиток: 1 \times 2 плитки вартістю рублів кожна (Петро розуміє, що ці плитки можна повернути на градусів і отримати 2 \times 1), та 1 \times 1 плитки вартістю рублів кожна. Петро не може розрізати плитку 1 \times 2 на дві 1 \times 1 плитки.
Визначте мінімальну суму грошей, яку Петро має витратити на ремонт.
У першому рядку вхідних даних записано числа: , , , (1 \leq N, M \leq 300, — цілі числа за модулем не більше ). Кожен з наступних рядків містить символів: "." (крапка) означає цілу плитку, а "*" (зірочка) — пошкоджену. Рядки можуть містити пробіли наприкінці. Файл може завершуватися порожніми рядками.
Виведіть одне число — мінімальну вартість заміни пошкоджених паркетних плиток (і лише їх).
Приклад 1