Problems
Filling with domino
Filling with domino
Given the size of the playing field $n \times m$, some cells of which are already paved. To fill the free neighboring cells with domino of dimensions $1 \times 2$ worth $a$ units. To fill one free square cell $1 \times 1$ worth $b$ units.
Determine the minimum sum of money to fill all the field.
\InputFile
The first line contains four numbers $n, m, a, b~(1 \le n, m \le 100, a, b$ are integers not greater than 1000 by absolute value). Each of the next $n$ lines contains $m$ symbols: character "\textbf{.}" (point) means the filled cell of the field, the character "\textbf{*}" (star) means the free cell.
\OutputFile
Find the minimum sum of money to fill all free cells of the field (and only them).
Input example #1
2 3 3 2 .** .*.
Output example #1
5
Input example #2
3 4 5 3 *..* **** ***.
Output example #2
23