D. Среди волков
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В игре, в которую вы недавно начали играть, есть прямоугольное клеточное поле. Поле состоит из $$$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$$$) — размер поля и соответствующие стоимости.

Следующие две строки описывают само поле: $$$j$$$-й символ в $$$i$$$-й строке — это '.', 'S' или 'W':

  • '.' означает, что клетка пустая;
  • 'S' означает, что клетка занята овцой; на поле есть ровно одна такая клетка;
  • 'W' означает, что клетка занята волком.

Дополнительные ограничения:

  • в клетках, соседних с клеткой овцы, нет волков;
  • сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.
Выходные данные

Для каждого набора входных данных выведите одно целое число — минимальную сумму денег, которую вы должны заплатить, чтобы спасти свою овцу.

Примеры
Входные данные
4
2 3 7
S.
..
2 3 7
S.
.W
2 7 3
S.
.W
4 999999999 1000000000
W.S.
W..W
Выходные данные
0
3
6
2999999997
Входные данные
2
6 6 7
W....W
W.S..W
6 6 7
W...WW
..S..W
Выходные данные
21
20
Примечание

Одну из оптимальных стратегий в первом тестовом наборе второго теста можно изобразить так:

W....W$$$\Rightarrow$$$W.#..W
W.S..WW#S#.W
Аналогично, один из ответов для второго набора:
W...WW$$$\Rightarrow$$$W..#WW
..S..W..S#.W
Здесь '#' означает ров, а 'W' означает истребленного волка.