Painting#4351
In the country of Olympia, the art of painting is highly esteemed. A painting is defined as any rectangle made up of black and white unit squares. The artist Olympus has decided to enhance his paintings by introducing a gray shade between the black and white colors. His vision is to have a gray line at the boundary of each black and white square, creating a smooth transition effect.
However, before proceeding with this work, Olympus realized that gray paint is quite costly. To economize, he considered the possibility of repainting some of the white squares to black and vice versa, aiming to minimize the overall paint expenses.
Your task is to write a program that, given the details of the current painting, determines the minimum cost required to enhance the painting.
The first line contains five natural numbers: , (1 \le N, M \le 70) representing the height and width of the painting, and , , (1 \le w, b, g \le 1000) representing the cost of painting one white unit square, one black unit square, and a gray line of unit length, respectively. The next lines each contain characters. The character denotes a black square, and denotes a white square.
Output a single integer — the minimum cost required to enhance the painting.
Example 1