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