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.

Input

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

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

Examples