Given the size of the playing field , some cells of which are already paved. To fill the free neighboring cells with domino of dimensions worth units. To fill one free square cell worth units.
Determine the minimum sum of money to fill all the field.
The first line contains four numbers are integers not greater than 1000 by absolute value). Each of the next lines contains 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).