← 返回题目列表

Codeforces · 1443/B

B. 拯救城市

中文机器翻译题面 查看原题

Bertown 是一座拥有 $$$n$$$ 建筑物呈直线的城市。

该市安全部门发现一些建筑物被埋有地雷。编译了一张地图,它是一个长度为 $$$n$$$ 的字符串,其中如果建筑物号 $$$i$$$ 下有地雷,则第 $$$i$$$ 个字符为“1”,否则为“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$$$。

输出

对于每个测试用例,输出一个整数——工兵必须支付的最小硬币数量。

示例

输入 #1

2
1 1
01000010
5 1
01101110

输出 #1

2
6

注意

在第二个测试用例中,如果我们在第四个建筑物下放置一个地雷然后激活它,那么场上的所有地雷都会被激活。此类操作的成本为 6,$$$b=1$$$ 硬币用于放置地雷,$$$a=5$$$ 硬币用于激活。