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

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

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

Input example #1

2 3 3 2 .** .*.

Output example #1

5

Input example #2

3 4 5 3 *..* **** ***.

Output example #2

23