Given the size of the playing field n×m, some cells of which are already paved. To fill the free neighboring cells with domino of dimensions 1×2 worth a units. To fill one free square cell 1×1 worth b units.
Determine the minimum sum of money to fill all the field.
The first line contains four numbers n,m,a,b (1≤n,m≤100,a,b are integers not greater than 1000 by absolute value). Each of the next n lines contains m symbols: character "." (point) means the filled cell of the field, the character "*" (star) means the free cell.
Find the minimum sum of money to fill all free cells of the field (and only them).