你计划在矩形画布上绘制一幅黑白画。画布由像素网格组成，初始状态全为白色，每个像素可以是黑色或白色。
你可以按任意顺序执行以下两种操作序列：
- 绘制水平或垂直的线段，宽度为单个像素，长度为两个或更多像素，颜色为黑色或白色。该操作的成本为线段长度（像素数）乘以指定的系数，再加上一个指定的常数。
- 绘制单个像素，颜色为黑色或白色。该操作具有指定的常数成本。
只要满足以下条件，你就可以覆盖已经绘制过的像素：
- 该像素之前最多被绘制过一次。多次覆盖会导致墨水层过厚，使画面看起来不美观。注意，用同一种颜色绘制像素也算作覆盖。例如，如果你已经将一个像素涂黑了两次，那么你就不能再将其涂成黑色或白色。
- 一旦像素被涂成白色，就不应该再用黑色墨水覆盖。由于白色墨水干燥时间很长，在同一个像素上覆盖黑色会使像素变成灰色，而不是黑色。反之，在已经涂黑的像素上覆盖白色则没有问题。
你的任务是计算绘制指定图像所需的最小总成本。
输入格式
输入包含单个测试用例。第一行包含五个整数 $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$) 是定义绘制成本的常数。绘制长度为 $l$ 的线段成本为 $a \cdot l + b$，绘制单个像素的成本为 $c$。这三个常数满足 $c \le a + b$。
接下来的 $n$ 行展示了你想要绘制的黑白图像。每一行包含一个长度为 $m$ 的字符串。第 $i$ 行字符串的第 $j$ 个字符，如果第 $i$ 行第 $j$ 列的像素应为黑色，则为 '#'，如果应为白色，则为 '.'。
输出格式
输出最小成本。
样例
样例 1
输入
3 3 1 2 3 .#. ### .#.
输出
10
样例 2
输入
2 7 0 1 1 ###.### ###.###
输出
3
样例 3
输入
5 5 1 4 4 ..#.. ..#.. ##.## ..#.. ..#..
输出
24
样例 4
输入
7 24 1 10 10 ###...###..#####....###. .#...#...#.#....#..#...# .#..#......#....#.#..... .#..#......#####..#..... .#..#......#......#..... .#...#...#.#.......#...# ###...###..#........###.
输出
256