Пол в некоторой комнате размером \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 В выходной файл выведите одно число -- минимальную сумму денег, имея которую можно заменить испорченные паркетины (и только их).