농지 평탄화

농부 존은 봄 수확을 앞두고 밭을 손보고 있다. 작년에는 트랙터가 언덕을 오르내리느라 연료를 예상보다 많이 써서 예산을 넘겼다.

수확할 때 트랙터는 밭 전체를 가로로도 세로로도 지나간다. 아래 그림에서 밝은 초록은 낮은 땅, 짙은 초록은 높은 땅이고, 빨간 선은 높이가 다른 두 칸이 맞닿은 경계다. 트랙터는 이 경계를 모두 넘어야 하므로 그림의 밭에서는 여덟 번 오르내린다.

밭은 $N \times M$ 격자로 나뉘어 있고, 각 칸의 높이는 낮음과 높음 두 가지뿐이다. 존은 씨를 뿌리기 전에 불도저를 불러 원하는 칸의 높이를 바꿀 수 있다. 한 칸을 낮음에서 높음으로, 또는 높음에서 낮음으로 바꾸는 데 $B$유로가 든다.

작업이 끝난 뒤, 변끼리 맞닿은 두 칸의 높이가 서로 다르면 그 경계마다 트랙터 연료비로 $A$유로가 더 든다.

따라서 존이 올해 내는 금액은 높이를 바꾼 칸의 수에 $B$를 곱한 값과, 작업이 끝난 밭에서 높이가 서로 다른 인접한 칸 쌍의 수에 $A$를 곱한 값의 합이다. 이 금액의 최솟값을 구하는 프로그램을 작성하시오.

첫째 줄에 네 정수 $N$, $M$, $A$, $B$가 공백으로 구분되어 주어진다. 밭의 크기는 $N \times M$이고, $A$는 높이가 다른 두 인접한 칸의 경계를 지날 때 드는 비용, $B$는 한 칸의 높이를 바꾸는 비용이다.

다음 $N$개 줄에는 각각 $M$개의 문자가 주어져 밭의 현재 상태를 나타낸다. .은 낮은 땅, #은 높은 땅이다.

존이 내야 하는 최소 금액을 한 줄에 출력한다.

• $1 \le N, M \le 50$ (밭의 크기)
• $1 \le A, B \le 100000$ (경계를 지나는 비용과 한 칸의 높이를 바꾸는 비용)

예제의 밭은 $5 \times 4$이다. 높이가 다른 두 칸의 경계를 지나는 데 1000유로, 한 칸의 높이를 바꾸는 데 2000유로가 든다.

답은 11000유로다. 외따로 떨어진 높은 칸 하나를 낮추는 데 2000유로, 남은 아홉 개의 경계를 지나는 연료비로 9000유로가 든다.

아무 칸도 바꾸지 않으면 12000유로, 높은 칸을 모두 낮추면 18000유로, 낮은 칸을 모두 높이면 22000유로가 든다.