泳池建造

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

泳池区域是一个 $w \times h$ 的矩形网格，由零个或多个（可能互不相连的）泳池组成。一个泳池由一个或多个连通的坑洞网格组成，这些坑洞稍后将被注满水。起初，你面对的是一块土地，每个网格要么是地上的坑洞（'.'），要么是平坦的草地（'#'）。为了将这块土地改造成泳池区域，你必须遵守以下规则：

• 你可以保持网格原样，这不需要任何费用。
• 如果网格最初是草地，你可以将其挖成坑洞，费用为 $d$ 欧元。
• 如果网格最初是坑洞，你可以将其填平并铺上草地，费用为 $f$ 欧元。
• 你必须在最终的草地网格和最终的坑洞网格之间的每一条公共边上放置特殊的边界元件，以确保水不会从泳池中泄漏。每个边界元件的费用为 $b$ 欧元。
• 泳池区域最外层的行和列必须始终是草地。

给定现有土地的布局，你的任务是计算建造出最便宜的泳池区域所需的成本。

输入格式

第一行包含一个正整数：测试用例的数量，最多为 100。每个测试用例包含：

• 一行包含两个整数 $w$ 和 $h$ ($2 \le w, h \le 50$)：建筑场地的宽度和高度。
• 一行包含三个整数 $d, f$ 和 $b$ ($1 \le d, f, b \le 10\,000$)：挖掘新坑洞、填平现有坑洞以及在泳池和草地网格之间建造边界元件的费用。
• $h$ 行，每行包含 $w$ 个字符，表示原始建筑场地的布局。

输出格式

对于每个测试用例：

• 输出一行一个整数：从原始土地建造出最便宜的泳池区域所需的成本。

样例

输入 1

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

输出 1

9
27
22