수영장 만들기

상근이는 정인이의 앞마당에 수영장을 만들려고 한다.

수영장 부지는 가로 $w$, 세로 $h$ 크기이며, $1 \times 1$ 크기의 정사각형 구역으로 나누어져 있다. 수영장은 $0$개 이상의 구멍 구역으로 이루어지며, 구멍에는 나중에 물을 채운다.

공사를 시작하기 전, 각 구역은 구멍(.) 또는 잔디(#) 중 하나이다. 이 땅을 수영장으로 만들 때에는 다음 규칙을 따라야 한다.

• 어떤 구역을 그대로 두는 데에는 비용이 들지 않는다.
• 잔디 구역을 파서 구멍으로 만드는 비용은 $d$원이다.
• 구멍 구역을 메우고 잔디를 심는 비용은 $f$원이다.
• 수영장의 경계가 되는 각 변, 즉 잔디 구역과 구멍 구역이 맞닿는 모든 변에는 물이 새지 않도록 방수 처리를 해야 하며, 한 변마다 $b$원이 든다.
• 완성된 부지에서 가장 바깥쪽 행과 열은 모두 잔디여야 한다.

부지의 초기 상태가 주어질 때, 수영장을 완성하는 데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. ($1 \le T \le 100$)

각 테스트 케이스의 첫째 줄에는 부지의 크기 $w$와 $h$가 공백으로 구분되어 주어진다. ($2 \le w, h \le 50$) 둘째 줄에는 세 정수 $d$, $f$, $b$가 주어진다. ($1 \le d, f, b \le 10000$) 이어지는 $h$개의 줄에는 부지의 초기 상태가 주어지며, 각 줄은 $w$개의 문자로 이루어진다. 문자 #는 잔디를, .는 구멍을 나타낸다.

각 테스트 케이스마다 수영장을 완성하는 데 드는 최소 비용을 한 줄에 하나씩 출력한다.