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

Бертаун это город, в котором находятся $$$n$$$ зданий, расположенных вдоль одной прямой.

Служба безопасности города обнаружила, что некоторые здания заминированы. Была составлена карта, представляющая из себя строку длиной $$$n$$$, где $$$i$$$-й символ равен «1», если под зданием номер $$$i$$$ находится мина и «0» в противном случае.

Лучший сапер Бертауна умеет активировать мины так, чтобы здания над ними не пострадали. Когда мина под зданием с номером $$$x$$$ активируется, она взрывается и активирует две соседние мины под зданиями с номерами $$$x-1$$$ и $$$x+1$$$ (если мины под зданием не было, то ничего не происходит). Таким образом, достаточно активировать одну любую мину на непрерывном отрезке из мин, чтобы активировать все мины этого отрезка. За ручную активацию одной мины сапер берет $$$a$$$ монет. Он может повторять эту операцию сколько угодно раз.

Также сапер может сам поместить мину под здание, где ее не было. За такую операцию он берет $$$b$$$ монет. Он также может повторять эту операцию сколько угодно раз.

Операции сапер может проводить в любом порядке.

Вы хотите взорвать все мины в городе, чтобы сделать его безопасным. Найдите минимальное количество монет, которое придется заплатить саперу, чтобы после его действий в городе не осталось мин.

Входные данные

В первой строке находится одно целое положительное число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов тестовых данных. Далее следуют $$$t$$$ наборов тестовых данных.

Каждый набор начинается со строки в которой записаны два целых числа $$$a$$$ и $$$b$$$ ($$$1 \le a, b \le 1000$$$) — стоимость активации и размещения одной мины соответственно.

В следующей строке записана карта мин в городе — строка, состоящая из нулей и единиц.

Сумма длин строк по всем наборам тестовых данных не превосходит $$$10^5$$$.

Выходные данные

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

Пример
Входные данные
2
1 1
01000010
5 1
01101110
Выходные данные
2
6
Примечание

Во втором наборе тестовых данных, если мы поместим мину под четвертое здание и после этого активируем ее, то активируются все мины на поле. Стоимость таких операций равна шести, $$$b=1$$$ монета за помещение мины и $$$a=5$$$ монет за активацию.