CF1443B Saving the City

Bertown 是一座有 $n$ 栋建筑物排成一条直线的城市。 城市的安全部门发现有些建筑物下被埋设了地雷。制作了一张地图，用一个长度为 $n$ 的字符串表示，第 $i$ 个字符为 "1" 表示第 $i$ 号建筑物下有地雷，为 "0" 表示没有地雷。 Bertown 最优秀的排雷专家知道如何引爆地雷而不损坏上方的建筑物。当编号为 $x$ 的建筑物下的地雷被引爆时，它会爆炸并激活相邻的编号为 $x-1$ 和 $x+1$ 的地雷（如果这些建筑物下有地雷的话，否则什么也不会发生）。因此，只需手动引爆连续一段地雷中的任意一个地雷，就可以引爆该段所有地雷。每手动引爆一个地雷，专家需要 $a$ 枚硬币。他可以重复进行此操作任意次。 此外，如果某栋建筑物下没有地雷，专家也可以在其下方埋设一个地雷。每埋设一个地雷需要 $b$ 枚硬币。他也可以重复进行此操作任意次。 专家可以以任意顺序进行这些操作。 你希望引爆城市中所有的地雷，使城市变得安全。请你计算专家需要支付的最少硬币数，使得经过操作后城市中不再有地雷。

第一行包含一个正整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。接下来有 $t$ 组测试用例。 每组测试用例的第一行包含两个整数 $a$ 和 $b$（$1 \le a, b \le 1000$），分别表示引爆一个地雷和埋设一个地雷的费用。 下一行包含一张城市地雷分布图——一个只包含数字 $0$ 和 $1$ 的字符串。 所有测试用例的字符串长度之和不超过 $10^5$。

对于每个测试用例，输出一个整数，表示专家需要支付的最少硬币数。

在第二个测试用例中，如果我们在第四栋建筑物下埋设一个地雷，然后引爆它，那么场上所有地雷都会被引爆。这样的操作费用为 $6$，即埋设地雷的费用 $b=1$ 和引爆的费用 $a=5$。 由 ChatGPT 4.1 翻译