410689: GYM104077 B Cells Coloring

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.

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 a line with a single number, representing the answer.

3 4 2 1
.***
*..*
**..

4

3 4 1 2
.***
*..*
**..

2