eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Испорченный паркет

Испорченный паркет

Лимит времени 2 секунды
Лимит использования памяти 64 MiB

Пол в некоторой комнате размером M×N замощен паркетом. При этом некоторые плитки паркета оказались испорчены. Петя решил сделать ремонт в этой комнате, заменив только испорченные клетки. Придя в магазин, он обнаружил, что паркетные плитки бывают двух типов – размера 1×2, которые стоят A рублей (немного подумав, Петя понял, что плитки 1×2 можно поворачивать на 90 градусов, получая тем самым плитки 2×1) и размера 1×1, которые стоят B рублей. Разрезать плитку размера 1×2 на две, размера 1×1 Петя не может.

Определите, какая минимальная сумма денег нужна Пете, чтобы сделать ремонт.

Входные данные

Первая строка входного файла содержит 4 числа N, M, A, B (1N, M300, A, B – целые числа, по модулю не превосходящие 1000). Каждая из последующих N строк содержит по M символов: символ "." (точка) обозначает неиспорченную плитку паркета, а символ "*" (звездочка) – испорченную. В конце строк могут идти незначащие пробелы. В конце файла могут быть пустые строки.

Выходные данные

В выходной файл выведите одно число – минимальную сумму денег, имея которую можно заменить испорченные паркетины (и только их).

Пример

Входные данные #1
10 10 0 1
*.*.*.*.*.
.*.*.*.*.*
*.*.*.*.*.
.*.*.*.*.*
*.*.*.*.*.
.*.*.*.*.*
*.*.*.*.*.
.*.*.*.*.*
*.*.*.*.*.
.*.*.*.*.*
Выходные данные #1
50