직선으로 그리기

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

다음 두 연산을 임의의 순서로 조합해서 적용할 수 있다.

• 가로 또는 세로 선분 위의 픽셀을 검은색 또는 흰색으로 칠한다. 선분의 너비는 픽셀 1개이고 길이는 픽셀 2개 이상이다. 이 연산의 비용은 $a \times L + b$이며, $L$은 선분의 픽셀 수다.
• 픽셀 하나를 검은색 또는 흰색으로 칠한다. 이 연산의 비용은 상수 $c$다.

이미 칠한 픽셀은 다음 조건을 지키면 덧칠할 수 있다.

• 픽셀은 그 전에 최대 한 번만 칠해졌어야 한다. 같은 색으로 칠하는 것도 덧칠에 포함된다. 예를 들어 픽셀을 검은색으로 두 번 칠했다면, 그 뒤로는 검은색으로도 흰색으로도 칠할 수 없다.
• 흰색으로 칠한 픽셀은 검은색으로 덧칠할 수 없다. 흰색 잉크는 마르는 데 매우 오래 걸려서, 검은색을 덧칠하면 검은색이 아니라 회색이 된다. 검은색 위에 흰색을 덧칠하는 것은 문제없다.

주어진 그림을 그리는 데 드는 최소 총비용을 구하라.

첫 줄에 정수 $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 \times L + b$이고, 픽셀 하나를 칠하는 비용은 $c$다. 이 상수들은 $c \le a + b$를 만족한다.

이어지는 $n$개의 줄에는 길이 $m$인 문자열이 하나씩 주어진다. $i$번째 문자열의 $j$번째 문자는 $i$행 $j$열 픽셀이 검은색이면 "#", 흰색이면 "."이다.

최소 비용을 출력한다.