Description

你计划在一块矩形画布上绘制一幅黑白画。这幅画将是一个由黑色或白色像素组成的网格阵列。你可以在初始为白色的画布上绘制黑色或白色的线条或点。

你可以按任意顺序应用以下两种操作的序列。

• 在水平或垂直的线段上绘制像素，线段宽度为单个像素，长度大于等于两个像素，可以是黑色或白色。此操作的成本与线段长度（像素数）乘以指定的系数成正比，再加上指定的固定成本。
• 绘制单个像素，可以是黑色或白色。此操作具有指定的固定成本。

只要满足以下条件，你可以覆盖绘制已绘制过的像素。

• 该像素之前最多被绘制过一次。覆盖绘制像素太多次会导致墨水层过厚，使画面看起来不美观。请注意，用相同颜色绘制像素也算作覆盖绘制。例如，如果你用黑色绘制了一个像素两次，那么你不能再将其绘制为黑色或白色。
• 一旦被绘制为白色的像素不应被黑色墨水覆盖绘制。因为白色墨水需要很长时间才能干透，覆盖绘制黑色会使像素变成灰色，而不是黑色。反之，即在已绘制为黑色的像素上绘制白色，则没有问题。

你的任务是计算绘制指定图像的最小总成本。

Input Format

输入包含单个测试用例。第一行包含五个整数 $n$、$m$、$a$、$b$ 和 $c$，其中 $n$ （$1 \le n \le 40$）和 $m$ （$1 \le m \le 40$）分别是画布的高度和宽度（以像素数计），$a$ （$0 \le a \le 40$）、$b$ （$0 \le b \le 40$）和 $c$ （$0 \le c \le 40$）是定义绘制成本的常数，如下所述。绘制长度为 $\ell$ 的线段成本为 $a\ell + b$，绘制单个像素的成本为 $c$。这三个常数满足 $c \le a + b$。

接下来的 $n$ 行显示你想要绘制的黑白图像。每行包含一个长度为 $m$ 的字符串。第 $i$ 行字符串的第 $j$ 个字符如果是 #，则表示第 $i$ 行第 $j$ 列的像素颜色应为黑色；如果是 .，则表示颜色应为白色。

Output Format

输出最小成本。

3 3 1 2 3
.#.
###
.#.

10

2 7 0 1 1
###.###
###.###

3

5 5 1 4 4
..#..
..#..
##.##
..#..
..#..

24

7 24 1 10 10
###...###..#####....###.
.#...#...#.#....#..#...#
.#..#......#....#.#.....
.#..#......#####..#.....
.#..#......#......#.....
.#...#...#.#.......#...#
###...###..#........###.

256