UVA1515 建造游泳池

给定一个 $n \times m$ 的矩阵（陆地），每个格子要么是草（用 `#` 代替），要么是水洼（用 `.` 代替）。你要将它变成游泳池。 有下述修改方法或要求： - 将**草地**变成**水洼**，要花费 $d$ 元。 - 将**水洼**变成**草地**，要花费 $f$ 元。 - 对矩阵边缘有要求，必须全部为草地。 - 要在水洼和草地之间修筑围墙。每个单位的围墙要花费 $b$ 元。 请你计算出最小花费。

第一行是一个整数 $T$，表示测试组数。 对于每组数据，第一行，给出矩阵的范围 $n$ 和 $m$（$2 \leq n,m \leq 50$）。 接下来依次给出三个整数 $d,f,b$（$1 \leq d,f,b \leq 10000$ ）。 最后给出 $n \times m$ 矩阵的具体信息。

每行一个整数，第 $i$ 行表示第 $i$ 组数据的最小花费。

## 样例输入： ```text 3 3 3 5 5 1 #.# #.# ### 5 4 1 8 1 #..## ##.## #.#.# ##### 2 2 27 11 11 #. .# ``` ## 样例输出 ```text 9 27 22 ```