B. Cells Coloring
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given an $$$n \times m$$$ grid. Some of the cells are obstacles, the others are empty. Choose a non-negative integer $$$k$$$ and color all empty cells with $$$k+1$$$ colors $$$0, 1, 2, \ldots k$$$. You can not color two cells in the same row or same column with the same non-zero color.

You are given two non-negative integers $$$c$$$ and $$$d$$$. For a coloring plan, define $$$z$$$ as the number of the cells with color $$$0$$$. Define the cost of the plan is $$$ck+dz$$$.

Find the minimum cost.

Input

The first line contains four integers $$$n$$$, $$$m$$$ ($$$1\leq n, m\leq 250$$$), $$$c$$$ and $$$d$$$ ($$$0\leq c, d\leq 10 ^ 9$$$).

The $$$i$$$-th line of the next $$$n$$$ lines contains a string of $$$m$$$ characters. The $$$j$$$-th character is '*' if the cell in the $$$i$$$-th row and the $$$j$$$-th column is an obstacle. The $$$j$$$-th character is '.' if the cell in the $$$i$$$-th row and the $$$j$$$-th column is empty.

Output

Output a line with a single number, representing the answer.

Examples
Input
3 4 2 1
.***
*..*
**..
Output
4
Input
3 4 1 2
.***
*..*
**..
Output
2