Зіпсований паркет
Підлога у деякій кімнаті розміром M×N замощена паркетом. При цьому деякі плитки паркету виявились зіпсованими. Петро вирішив зробити ремонт у цій кімнаті, замінивши лише зіпсовані клітинки. Прийшовши до магазину, він виявив, що паркетні плитки бувають двох типів – розміром 1×2, які коштують A рублів (трохи подумавши, Петро зрозумів, что плитки 1×2 можно повертати на 90 градусів, отримуючи при цьому плитки 2×1) і розміром 1×1, які коштують B рублів. Розрізати плитку розміром 1×2 на дві, розміром 1×1 Петро не може.
Визначте, яка мінімальна сума грошей потрібна Петру, щоб зробити ремонт.
Вхідні дані
Перший рядок вхідного файлу містить 4 числа N, M, A, B (1 ≤ N, M ≤ 300, A, B – цілі числа, які по модулю не перевищують 1000). Кожен з наступних N рядків містить по M символів: символ "." (крапка) позначає незіпсовану плитку паркету, а символ "*" (зірочка) – зіпсовану. У кінці рядків можуть йти незначущі пропуски. У кінці файлу можуть бути порожні рядки.
Вихідні дані
У вихідний файл виведіть одне число – мінімальну суму грошей, маючи яку можна замінити зіпсовані паркетини (і лише їх).