Competitions

# Maximum flow and matchings

# Filling with domino

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.

## Input data

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.

## 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