eolymp
bolt
Try our new interface for solving problems
Problems

Filling with domino

Filling with domino

Time limit 1 second
Memory limit 128 MiB

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.

Input data

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 "." (point) means the filled cell of the field, the character "*" (star) means the free cell.

Output data

Find the minimum sum of money to fill all free cells of the field (and only them).

Examples

Input example #1
2 3 3 2
.**
.*.
Output example #1
5
Input example #2
3 4 5 3
*..*
****
***.
Output example #2
23