CF2011D Among Wolves

在你最近开始玩的一个游戏中，有一个可以表示为矩形网格的字段。该字段有2行n列，总共2n个单元格。 有些牢房是空的，但有些被狼占据了。在游戏开始时，你在某个牢房里有一只羊，你想把它从狼手中救出来。 狼会在晚上攻击你，所以你还有一些时间做准备。你有两种方法对付狼： 1.你向猎人支付h硬币，然后选择一个被狼占据的牢房。猎人将清除细胞，消灭其中的狼。 2.你向建筑商支付b币，然后选择一个空单元格。建筑商将在选定的牢房里挖一条狼无法穿过的沟渠。 您可以任意次数和顺序使用上述两种方法。假设狼可以到达绵羊，如果有一条从狼的牢房开始到绵羊牢房结束的路径。此路径不应包含任何带有沟槽的单元格，路径中的每两个连续单元格应

第一行包含一个整数t（1≤t≤1200—测试用例的数量。接下来是独立案例。 每个测试用例的第一行包含三个整数n、h和b（2≤n≤10^5;1≤h,b≤10^9)—电网的规模和相应的成本。 接下来的两行包含网格的描述。第二行中的第j个字符是“.”，'S'或'W'： ``` '.' 意味着该单元格是空的； "S"表示牢房被绵羊占据；网格上恰好有一个这样的单元； "W"表示牢房被狼占据。 ``` 附加约束： ``` 绵羊牢房附近的牢房里没有狼； 所有测试用例的n总和不超过2*10^5. ```

对于每个测试用例，打印一个整数—你应该为拯救你的羊而支付的最小总金额。

One of the optimal strategies in the first test case of the second test can be shown like this: W....W $ \Rightarrow $ W.#..WW.S..WW#S#.W Analogically, one of the answers for the second case is the following: W...WW $ \Rightarrow $ W..#WW..S..W..S#.W Here, '\#' means a trench and 'W' means an eradicated wolf.