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