在您最近开始玩的游戏中,有一个可以表示为矩形网格的字段。该字段有 $$$2$$$ 行和 $$$n$$$ 列 - 总共 $$$2n$$$ 个单元格。
有些牢房是空的,但有些却被狼占据了。在游戏开始时,你在某个牢房里有一只羊,你想把它从狼手中救出来。
狼会在晚上袭击你,所以你还有一些准备时间。对付狼有两种方法:
1. 你向猎人支付 $$$h$$$ 硬币并选择一个被狼占据的牢房。猎人将清理牢房,消灭里面的狼。
2. 您向建造者支付 $$$b$$$ 硬币并选择一个空单元格。建造者将在选定的牢房中挖一条狼无法穿越的沟渠。
假设有一条路径从狼的牢房开始并在羊的牢房结束,那么狼就可以到达羊。该路径不应包含任何带沟槽的单元,并且路径中的每两个连续单元应是相邻的(共享一侧)。
为了确保没有一只狼能够到达羊的身边,您至少需要支付多少钱?
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1200$$$) — 测试用例的数量。接下来是 $$$t$$$ 独立案例。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$h$$$ 和 $$$b$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le h, b \le 10^9$$$) — 网格的大小和相应的成本。
接下来的两行包含网格的描述。第 $$$i$$$ 行中的第 $$$j$$$ 字符是 '.'、'S' 或 'W':
- '.'表示单元格是空的;
- 'S' 表示该单元格被羊占用;网格上只有一个这样的单元格;
- 'W' 表示该单元格被狼占据。
附加限制:
- 与羊格相邻的格子中没有狼;
- 所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - 您为拯救羊而应支付的最低总金额。
示例
输入 #1
4 2 3 7 S. .. 2 3 7 S. .W 2 7 3 S. .W 4 999999999 1000000000 W.S. W..W
输出 #1
0 3 6 2999999997
输入 #2
2 6 6 7 W....W W.S..W 6 6 7 W...WW ..S..W
输出 #2
21 20
注意
第二个测试的第一个测试用例中的最佳策略之一可以如下所示:
W....W$$$\右箭头$$$W.#..WW.S..WW#S#.W
W...WW$$$\右箭头$$$W..#WW..S..W..S#.W