Minimum Cost Grid Coloring

You are given an \(n \times m\) grid. Some cells are obstacles (denoted by #) and the others are empty (denoted by .). You must choose a non-negative integer \(k\) and color all empty cells using \(k+1\) colors: \(0,1,2,\dots,k\). The rule is that in each row and each column, no two cells may share the same non-zero color. (Cells colored \(0\) have no such restriction.)

You are also given two non-negative integers \(c\) and \(d\). For any valid coloring plan, let \(z\) be the number of cells with color \(0\), and define the cost as \[ \text{cost} = c\,k + d\,z.\] Find the minimum possible cost.

Note: Once you choose \(k\), you are allowed to assign non-zero colors to some of the empty cells subject to the constraint that for each non-zero color, no two cells in the same row or same column share that color. Equivalently, if you decide to color a cell with a non-zero color, then across empty cells you can choose a set of cells such that each row and each column is used at most once for each non-zero color. In other words, if you let \(M(k)\) be the maximum number of empty cells that can be assigned non-zero colors when each row and column can be used at most \(k\) times (this is a bipartite \(b\)-matching problem with \(b= k\)), then the number of cells colored 0 is \(z = (\text{\# empty cells}) - M(k)\), and the cost is \[ c\,k + d\,(E - M(k)). \] Your task is to choose \(k\) (and the corresponding assignment) to minimize this cost.

inputFormat

The first line contains four integers n m c d (1 ≤ n,m ≤ maxn, 0 ≤ c,d ≤ 10^9). Each of the next n lines contains a string of length m consisting of characters . and #, representing the grid. Here, . denotes an empty cell and # denotes an obstacle.

outputFormat

Output a single integer: the minimum cost.

sample

2 2 1 2
..
.#

2