您负责沿道路安装天然气管道。让我们将道路(为简单起见)视为 $$$OX$$$ 轴上的一段 $$$[0, n]$$$ 。道路可以有多个十字路口,但为了简单起见,我们将每个十字路口表示为整数 $$$x$$$ 的区间 $$$(x, x + 1)$$$。因此,我们可以将道路表示为由$$$n$$$字符组成的二进制字符串,其中字符0表示当前区间不包含十字路口,1表示存在十字路口。
通常,我们可以在$$$1$$$单位的高度上沿道路安装管道,并在每个整数点处设置支撑柱(因此,如果我们负责$$$[0, n]$$$道路,则必须安装$$$n + 1$$$支柱)。但在十字路口我们应该把管道抬高到$$$2$$$的高度,这样管道就不会阻碍汽车的通行。
我们可以插入几条之字形的线。每个zig-zag可以表示为一个线段$$$[x, x + 1]$$$,整数$$$x$$$由三部分组成:$$$0.5$$$水平管道单位+$$$1$$$垂直管道单位+$$$0.5$$$水平管道。请注意,如果管道当前的高度为 $$$2$$$,则支撑管道的支柱的长度也应等于 $$$2$$$ 单位。
每单位天然气管道的成本为 $$$a$$$ 布尔,每单位支柱的成本为 $$$b$$$ 布尔。因此,将整个管道设置在 $$$2$$$ 高度上并不总是最佳的。找到成本尽可能最小的管道形状并计算该成本。
请注意,您必须在高度 $$$1$$$ 上开始和结束管道,并且还保证输入字符串的第一个和最后一个字符等于 0。
输入
第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 100$$$) — 查询数。接下来的 $$$2 \cdot T$$$ 行包含独立查询 - 每两行一个查询。
第一行包含三个整数 $$$n$$$, $$$a$$$, $$$b$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le a \le 10^8$$$, $$$1 \le b \le 10^8$$$) — 道路的长度,一个单位管道的成本和分别是一个单位支柱的成本。
第二行包含二进制字符串 $$$s$$$ ($$$|s| = n$$$, $$$s_i \in \{0, 1\}$$$, $$$s_1 = s_n = 0$$$) — 道路的描述。
保证所有字符串$$$s$$$的总长度不超过$$$2 \cdot 10^5$$$。
输出
打印 $$$T$$$ 整数 — 每个查询一个。对于每个查询,打印所构建管道的最小可能成本。
示例
输入 #1
4 8 2 5 00110010 8 1 1 00110010 9 100000000 100000000 010101010 2 5 1 00
输出 #1
94 25 2900000000 13
注意
第一个查询的最佳管道如上图所示。
第二个查询的最佳管道如下图所示:
第三个查询的最佳(也是唯一可能的)管道如下所示:
第四个查询的最佳管道如下所示: