Painting
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 to create a smooth transition effect.
However, before proceeding with his 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 reduce the overall paint expenses.
Your task is to write a program that, given the details of the current painting, calculates the minimum cost required to enhance the painting.
Input
The first line contains five natural numbers: N, M (1 ≤ N, M ≤ 70) representing the height and width of the painting, and w, b, g (1 ≤ w, b, g ≤ 1000) representing the cost of painting one white unit square, one black unit square, and a gray line of unit length, respectively. This is followed by N rows, each containing M characters. The character B denotes a black square, while W denotes a white square.
Output
Output a single integer, which is the minimum cost required to enhance the painting.