시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 53 17 11 28.947%

문제

상근이는 사람들에게 수영장을 만들어주고 있다. 이번에는 정인이의 앞 마당에 수영장을 만들어 주려고 한다.

수영장 부지는 w×h크기이고, 1×1 크기의 정사각형 구역으로 나누어져 있다.수영장은 0개 또는 그 이상의 구멍 구역으로 이루어져 있다. 구멍을 뚫은 곳에는 나중에 물이 채워질 예정이다.

수영장을 만들기 전에 각 구역은 구멍('.')이거나 잔디('#')이다. 이 땅을 수영장으로 만드려면 아래와 같은 규칙을 지켜야 한다.

  • 구역을 그 자체로 놔둘 수 있다. 이 때 드는 비용은 없다.
  • 잔디였던 구역에 구멍을 파는데 드는 비용은 d원이다.
  • 구멍이였던 구역에 구멍을 막고 잔디를 심는데 드는 비용은 f원이다.
  • 수영장의 경계가 되는 각 변(잔디와 구멍 사이)에는 물이 세지 않기 위한 경계 처리를 해야 한다. 이 작업은 한 변당 b원이 든다.
  • 수영장 부지의 가장 바깥 행과 열은 잔디이어야 한다.

현재 수영장 부지의 땅 정보가 주어졌을 때, 수영장을 만드는데 가장 싼 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 100개를 넘지 않는다.

각 테스트 케이스의 첫째 줄에는 수영장 부지의 크기 w와 h가 주어진다. (2 ≤ w, h ≤ 50) 다음 줄에는 d, f, b가 주어진다. (1 ≤ d, f, b ≤ 10,000) 다음 h개 줄에는 수영장을 만들 부지의 정보가 주어진다.

출력

각 테스트 케이스에 대해서, 수영장을 만드는데 드는 비용의 최소값을 출력한다. 

예제 입력

3
3 3
5 5 1
#.#
#.#
###
5 4
1 8 1
#..##
##.##
#.#.#
#####
2 2
27 11 11
#.
.#

예제 출력

9
27
22

힌트

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2011 F번