Planujesz namalować czarno-biały obraz na prostokątnym płótnie. Obraz będzie siatką pikseli, z których każdy jest czarny albo biały. Na początkowo białym płótnie możesz malować czarne lub białe linie albo punkty.

Możesz wykonać ciąg następujących dwóch operacji w dowolnej kolejności.

• Malowanie pikseli na poziomym lub pionowym odcinku o szerokości jednego piksela i długości co najmniej dwóch pikseli na czarno albo biało. Koszt tej operacji jest proporcjonalny do długości odcinka (liczby pikseli): jest to długość pomnożona przez określony współczynnik, powiększona o określony stały koszt.

• Malowanie pojedynczego piksela na czarno albo biało. Ta operacja ma określony stały koszt.

Możesz ponownie malować już pomalowane piksele, o ile spełnione są następujące warunki.

• Piksel był wcześniej malowany co najwyżej raz. Zbyt wiele warstw farby na pikselu sprawia, że stają się one za grube i obraz wygląda brzydko. Zauważ, że malowanie piksela tym samym kolorem również liczy się jako ponowne malowanie. Na przykład, jeśli piksel pomalowano dwa razy na czarno, nie można go już pomalować ani na czarno, ani na biało.

• Piksela pomalowanego na biało nie wolno ponownie malować czarną farbą. Biała farba schnie bardzo długo, więc pomalowanie tego samego piksela na czarno sprawiłoby, że stałby się szary zamiast czarny. Odwrotna operacja, czyli malowanie na biało piksela już pomalowanego na czarno, nie stanowi problemu.

Twoim zadaniem jest obliczenie minimalnego łącznego kosztu namalowania podanego obrazu.

Wejście

Wejście zawiera jeden przypadek testowy. Pierwszy wiersz zawiera pięć liczb całkowitych $n,m,a,b,c$, gdzie $n$ ($1 \le n \le 40$) i $m$ ($1 \le m \le 40$) oznaczają wysokość i szerokość płótna w pikselach, a $a$ ($0 \le a \le 40$), $b$ ($0 \le b \le 40$) i $c$ ($0 \le c \le 40$) są stałymi określającymi koszty malowania w następujący sposób. Namalowanie odcinka długości $l$ kosztuje $a\cdot l+b$, a pojedynczego piksela kosztuje $c$. Te trzy stałe spełniają $c \le a+b$.

Następne $n$ wierszy opisuje czarno-biały obraz, który chcesz namalować. Każdy wiersz zawiera ciąg długości $m$. $j$-ty znak $i$-tego ciągu to #, jeśli piksel w $i$-tym wierszu i $j$-tej kolumnie ma być czarny, albo ., jeśli ma być biały.

Wyjście

Wypisz minimalny koszt.

Przykład

Wejście 1

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

Wyjście 1

10

Wejście 2

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

Wyjście 2

3

Wejście 3

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

Wyjście 3

24

Wejście 4

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

Wyjście 4

256