Making a Digram

In 2021, making a digram on the spot became a basic skill for Koreans. We want to draw a digram on the $n \times m$ grid in front of us.

A digram is defined as a shape made by joining seven $k \times k$ squares. The following are digrams for $k=1$ and $k=2$.

Examples of shapes that are not digrams are as follows.

Not made of seven $k \times k$ squares	A digram cannot be flipped or rotated

Some cells of the grid are already colored black. Painting a white cell black costs $a$, and erasing a black cell to make it white costs $b$. Write a program that finds the minimum cost needed so that the black cells form a digram.

The position and size of the digram are not restricted, but it cannot be flipped or rotated, and it must not go outside the grid. Also, every black cell must be included in the digram, and every cell not included in the digram must be white.

The first line gives the size of the grid, $n, m$.

The second line gives the costs $a, b$ of changing a cell's color.

The next $n$ lines each give a string of length $m$. # is a cell colored black, and . is a white cell.

On the first line, print the minimum cost to make a digram.

• $3 \le n,m \le 20$
• $1 \le a,b \le 1000$