CF1207C.Gas Pipeline

You are responsible for installing a gas pipeline along a road. Let's consider the road (for simplicity) as a segment $[0, n]$ on $OX$ axis. The road can have several crossroads, but for simplicity, we'll denote each crossroad as an interval $(x, x + 1)$ with integer $x$. So we can represent the road as a binary string consisting of $n$ characters, where character 0 means that current interval doesn't contain a crossroad, and 1 means that there is a crossroad.

Usually, we can install the pipeline along the road on height of $1$ unit with supporting pillars in each integer point (so, if we are responsible for $[0, n]$ road, we must install $n + 1$ pillars). But on crossroads we should lift the pipeline up to the height $2$, so the pipeline won't obstruct the way for cars.

We can do so inserting several zig-zag-like lines. Each zig-zag can be represented as a segment $[x, x + 1]$ with integer $x$ consisting of three parts: $0.5$ units of horizontal pipe + $1$ unit of vertical pipe + $0.5$ of horizontal. Note that if pipeline is currently on height $2$, the pillars that support it should also have length equal to $2$ units.

Each unit of gas pipeline costs us $a$ bourles, and each unit of pillar — $b$ bourles. So, it's not always optimal to make the whole pipeline on the height $2$. Find the shape of the pipeline with minimum possible cost and calculate that cost.

Note that you must start and finish the pipeline on height $1$ and, also, it's guaranteed that the first and last characters of the input string are equal to 0.

你需要负责沿一条道路铺设一条燃气管道。为简化问题，我们将道路视为 $OX$ 轴上的线段 $[0, n]$。道路上可能存在多个十字路口；为简化起见，我们将每个十字路口表示为形如 $(x, x + 1)$ 的开区间，其中 $x$ 为整数。因此，整条道路可用一个长度为 $n$ 的二进制字符串表示：字符 0 表示当前区间不包含十字路口，字符 1 表示该区间存在十字路口。

通常，我们可以将管道铺设在高度为 $1$ 的位置，并在每个整数坐标点（即 $x = 0, 1, \dots, n$）处设置支撑立柱（因此，对于 $[0, n]$ 这段道路，必须安装 $n + 1$ 根立柱）。但在十字路口处，我们必须将管道抬升至高度 $2$，以避免阻碍车辆通行。

我们可通过插入若干“之”字形线段来实现抬升。每个“之”字形可表示为某个整数 $x$ 对应的区间 $[x, x + 1]$ 上的三段结构：$0.5$ 单位水平管道 + $1$ 单位垂直管道 + $0.5$ 单位水平管道。注意：若管道当前处于高度 $2$，则其支撑立柱的长度也必须为 $2$ 单位。

每单位长度的燃气管道花费 $a$ 博尔勒斯（bourles），每单位长度的立柱花费 $b$ 博尔勒斯。因此，将整条管道始终铺设在高度 $2$ 并不一定是最优方案。请找出使总成本最小的管道铺设方案，并计算该最小成本。

注意：管道必须从高度 $1$ 开始，也在高度 $1$ 处结束；此外，输入字符串的第一个和最后一个字符保证均为 0。

The fist line contains one integer $T$ ($1 \le T \le 100$) — the number of queries. Next $2 \cdot T$ lines contain independent queries — one query per two lines.

The first line contains three integers $n$, $a$, $b$ ($2 \le n \le 2 \cdot 10^5$, $1 \le a \le 10^8$, $1 \le b \le 10^8$) — the length of the road, the cost of one unit of the pipeline and the cost of one unit of the pillar, respectively.

The second line contains binary string $s$ ($|s| = n$, $s_i \in {0, 1}$, $s_1 = s_n = 0$) — the description of the road.

It's guaranteed that the total length of all strings $s$ doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $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$。

Print $T$ integers — one per query. For each query print the minimum possible cost of the constructed pipeline.

输出 $T$ 个整数——每个查询对应一个整数。对于每个查询，输出所构建管道的最小可能成本。

The optimal pipeline for the first query is shown at the picture above.

The optimal pipeline for the second query is pictured below:

The optimal (and the only possible) pipeline for the third query is shown below:

The optimal pipeline for the fourth query is shown below:

第一个查询的最优流水线如上图所示。

第二个查询的最优流水线如下图所示：

第三个查询的最优（且唯一可能的）流水线如下图所示：

第四个查询的最优流水线如下图所示：