问题背景

我们称一个字符串为一个 01字符串 当且仅当该字符串仅由字符 '0' 和 '1' 构成。

题目描述

给定一个 01字符串 $s$，你可以对字符串 $s$ 进行任意次如下两种类型的操作：

• 操作1：选择字符串 $s$ 中连续的一段字符 '1'，并将这一段字符 '1' 全都变成字符 '0' $\Rightarrow$ 进行一次该操作的花费为 $a$；
• 操作2：选择字符串 $s$ 中恰好一个字符 '0'，并将该字符 '0' 修改为字符 '1' $\Rightarrow$ 进行一次该操作的花费为 $b$。

你希望使用最小的总花费使字符串 $s$ 中的每个字符都变为 '0'。

求：使字符串 $s$ 中的每个字符都变为 '0' 所需的最小总花费？

输入格式

输入包含多组测试数据。

输入的第一行包含一个整数 $t(1 \le t \le 1000)$，表示测试数据组数。

接下来每组测试数据包含两行。其中：

第一行包含两个整数 $a$ 和 $b$，以一个空格分隔（$1 \le a,b \le 1000$），分别表示将一段字符 '1' 变为 '0' 所需的花费，以及将一个字符 '0' 变为 '1' 所需的花费。

第二行包含一个 01字符串 $s$。$s$ 仅由字符 '0' 和 '1' 构成且长度不超过 $10^5$。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示使字符串 $s$ 中的每个字符都变为 '0' 所需的最小总花费。

2
1 1
01000010
5 1
01101110

2
6

说明/提示

样例解释

设 $s$ 的下标从 $1$ 开始，且用 $s[i]$ 表示字符串 $s$ 的第 $i$ 个字符，用 $s[i..j]$ 表示字符串 $s$ 的从第 $i$ 个字符到第 $j$ 个字符（包含第 $i$ 和 $j$ 个字符）的子串,则：

对于第一组测试数据，最优方案是：

1. 先使用操作1将 $s[2..2]$ 置为 '0'，花费 $1$；
2. 再使用操作1将 $s[7..7]$ 置为 '0'，花费 $1$。

总花费为 $1 + 1 = 2$。

对于第二组测试数据，最优方案是;

1. 先使用操作2将 $s[4]$ 置为 '1'，花费 $1$；
2. 再使用操作1将 $s[2..7]$ 置为 '0'，花费 $5$。

总花费为 $1 + 5 = 6$。

数据规模与约定

设 $|s|$ 表示字符串 $s$ 的长度，则：

• 对于 $30\%$ 的数据，$t,a,b,|s| \le 10$
• 对于 $60\%$ 的数据，$t,a,b\le 100; |s| \le 1000$
• 对于 $100\%$ 的数据，$1 \le t,a,b \le 1000; 1 \le |s| \le 10^5$，且所有测试数据的 $|s|$ 之和不超过 $10^5$