В игре, в которую вы недавно начали играть, есть прямоугольное клеточное поле. Поле состоит из \(2\) строк и \(n\) столбцов — всего \(2n\) клеток.
Некоторые клетки пустые, но некоторые — заняты волками. В начале игры у вас есть одна овца, расположенная в какой-то клетке, и вы хотите спасти её от волков.
Волки атакуют вас ночью, так что у вас еще есть время для подготовки. У вас есть два способа справиться с волками:
- Вы платите \(h\) монет охотникам и выбираете клетку, занятую волком. Охотники очистят клетку, истребив волка в ней.
- Вы платите \(b\) монет строителям и выбираете пустую клетку. Строители выкопают ров в выбранной клетке, который волки не смогут пересечь.
Вы можете использовать оба упомянутых метода любое количество раз и в любом порядке.
Будем считать, что волк может добраться до овцы, если существует путь по клеткам, который начинается в клетке волка и заканчивается в клетке овцы. При этом путь не содержит клеток со рвами, и каждые две последовательные клетки в пути являются соседями (то есть имеют общую сторону).
Какую минимальную сумму денег вы должны заплатить, чтобы гарантировать, что ни один из волков не сможет добраться до овцы?
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальную сумму денег, которую вы должны заплатить, чтобы спасти свою овцу.
Примечание
Одну из оптимальных стратегий в первом тестовом наборе второго теста можно изобразить так:
| W....W | \(\Rightarrow\) | W.#..W |
| W.S..W | | W#S#.W |
Аналогично, один из ответов для второго набора:
| W...WW | \(\Rightarrow\) | W..#WW |
| ..S..W | | ..S#.W |
Здесь '
#' означает ров, а '
W' означает истребленного волка.