9276 - 建造泳池

您正在为国际游泳池建设公司工作，这是一家专门建造游泳池的建筑公司。一个新客户想要建造几个新的泳池区域。

一个泳池区域是一个w × h方块的矩形网格，由零个或多个泳池组成。一个泳池由一个或多个相连的洞口方块组成，以后将会装修后被水填满。一开始，你拥有一块土地，其中每个方块要么是地面上的洞（'.'），要么是平坦的草地（'#'）。为了将这块土地转变为一个泳池区域，你必须遵循以下规则：

• 你可以保持一个方块不变。这不需要任何费用。
• 如果一开始方块是草地，你可以在那里挖一个洞。这需要花费d元。
• 如果一开始方块是一个洞，你可以填上洞并在上面种上草。这需要花费f元。

你必须在每个草地方块和最终的洞口方块之间装修（涂水泥，防水，贴瓷砖等），以保证水不会从泳池中泄漏。每一个长度的边界都要花费b元。 泳池区域的最外层的行和列必须始终是草地。 你的任务是根据现有土地的布局计算建造最便宜的可能泳池区域的费用。

第一行是一个正整数：测试用例的数量（数量在100之内）。之后对于每个测试用例：

一行包含两个整数w和h（2 ≤ w, h ≤ 100）：建筑场地的宽度和高度。
一行包含三个整数d，f和b（1 ≤ d, f, b ≤ 10,000）：挖掘新洞、填补现有洞和在泳池和草地方块之间建立边界元素的成本。
h行，每行w个字符，表示原始建筑场地的布局。

每个测试用例：

一行包含一个整数：从原始土地建造最便宜泳池区域的成本。

对于测试数据的样例1：需要把第1行第2列的洞填上草，需要5元。还需要把2行第二轮的洞作为泳池，有4个单位长度的边需要装修，需要4元。总计9元。
对于测试数据的样例2：需要把第1行第2列和第3列的洞填上草，需要16元。需要把第3行第3列的草地挖洞，需要花费1元。最后需要把第2行第3列、第3行第2列、第3行第3列、第3行第4列的洞作为泳池，有10个单位长度的边需要装修（见下图，是一个类似“凸”字形的泳池），需要10元。总计27元。

其它比赛