직사각형 캔버스에 흑백 그림을 그리려고 한다. 그림은 각 픽셀이 검은색 또는 흰색인 격자 배열이다. 처음에는 흰색인 캔버스에 검은색이나 흰색 선 또는 점을 칠할 수 있다.

다음 두 연산을 임의의 순서로 여러 번 수행할 수 있다.

• 너비가 한 픽셀이고 길이가 두 픽셀 이상인 수평 또는 수직 선분의 픽셀들을 검은색이나 흰색으로 칠한다. 이 연산의 비용은 선분의 길이(픽셀 수)에 지정된 계수를 곱한 값에 지정된 상수 비용을 더한 값이다.

• 한 픽셀을 검은색이나 흰색으로 칠한다. 이 연산에는 지정된 상수 비용이 든다.

다음 조건을 만족하면 이미 칠한 픽셀을 덧칠할 수 있다.

• 그 픽셀은 이전에 최대 한 번 칠해졌어야 한다. 한 픽셀을 너무 많이 덧칠하면 잉크 층이 너무 두꺼워져 그림이 보기 흉해진다. 같은 색으로 칠하는 것도 덧칠로 센다는 점에 유의하라. 예를 들어 한 픽셀을 검은색으로 두 번 칠했다면 더 이상 검은색으로도 흰색으로도 칠할 수 없다.

• 한 번 흰색으로 칠한 픽셀은 검은색 잉크로 덧칠하면 안 된다. 흰색 잉크는 마르는 데 매우 오래 걸리므로 같은 픽셀을 검은색으로 덧칠하면 검은색이 아니라 회색이 된다. 반대로, 이미 검은색으로 칠한 픽셀을 흰색으로 덧칠하는 것은 문제가 없다.

주어진 이미지를 그리는 데 필요한 최소 총비용을 계산하라.

입력

입력은 하나의 테스트 케이스로 이루어진다. 첫 줄에는 정수 $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
.#.
###
.#.

출력 1

10

입력 2

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

출력 2

3

입력 3

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

출력 3

24

입력 4

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

출력 4

256