Бертаун это город, в котором находятся \(n\) зданий, расположенных вдоль одной прямой.
Служба безопасности города обнаружила, что некоторые здания заминированы. Была составлена карта, представляющая из себя строку длиной \(n\), где \(i\)-й символ равен «1», если под зданием номер \(i\) находится мина и «0» в противном случае.
Лучший сапер Бертауна умеет активировать мины так, чтобы здания над ними не пострадали. Когда мина под зданием с номером \(x\) активируется, она взрывается и активирует две соседние мины под зданиями с номерами \(x-1\) и \(x+1\) (если мины под зданием не было, то ничего не происходит). Таким образом, достаточно активировать одну любую мину на непрерывном отрезке из мин, чтобы активировать все мины этого отрезка. За ручную активацию одной мины сапер берет \(a\) монет. Он может повторять эту операцию сколько угодно раз.
Также сапер может сам поместить мину под здание, где ее не было. За такую операцию он берет \(b\) монет. Он также может повторять эту операцию сколько угодно раз.
Операции сапер может проводить в любом порядке.
Вы хотите взорвать все мины в городе, чтобы сделать его безопасным. Найдите минимальное количество монет, которое придется заплатить саперу, чтобы после его действий в городе не осталось мин.
Примечание
Во втором наборе тестовых данных, если мы поместим мину под четвертое здание и после этого активируем ее, то активируются все мины на поле. Стоимость таких операций равна шести, \(b=1\) монета за помещение мины и \(a=5\) монет за активацию.