Draw in Straight Lines

You plan to draw a black-and-white painting on a rectangular canvas. The painting is a grid of pixels, each either black or white. You can paint black or white lines or dots on the initially white canvas.

You can apply a sequence of the following two operations in any order.

• Paint pixels on a horizontal or vertical line segment, one pixel wide and two or more pixels long, either black or white. This operation costs $a \times L + b$, where $L$ is the number of pixels in the segment.
• Paint a single pixel, either black or white. This operation has a constant cost of $c$.

You can overpaint already painted pixels as long as the following conditions hold.

• A pixel can have been painted at most once before. Overpainting a pixel too many times makes the ink layers too thick and the picture ugly. Painting a pixel with the same color also counts as overpainting. For example, if you painted a pixel black twice, you can no longer paint it black or white.
• A pixel painted white cannot be overpainted with black. White ink takes a very long time to dry, so black over white would look gray instead of black. Painting white over black is fine.

Your task is to compute the minimum total cost to draw the specified image.

The first line contains five integers $n$, $m$, $a$, $b$, and $c$. $n$ ($1 \le n \le 40$) and $m$ ($1 \le m \le 40$) are the height and width of the canvas in pixels. $a$ ($0 \le a \le 40$), $b$ ($0 \le b \le 40$), and $c$ ($0 \le c \le 40$) define the painting costs. A line segment of length $L$ costs $a \times L + b$, and a single pixel costs $c$. These constants satisfy $c \le a + b$.

The next $n$ lines each contain a string of length $m$. The $j$-th character of the $i$-th string is "#" if the pixel in row $i$, column $j$ should be black, and "." if it should be white.

Output the minimum cost.