CF1415C.Bouncing Ball

You're creating a game level for some mobile game. The level should contain some number of cells aligned in a row from left to right and numbered with consecutive integers starting from $1$, and in each cell you can either put a platform or leave it empty.

In order to pass a level, a player must throw a ball from the left so that it first lands on a platform in the cell $p$, then bounces off it, then bounces off a platform in the cell $(p + k)$, then a platform in the cell $(p + 2k)$, and so on every $k$-th platform until it goes farther than the last cell. If any of these cells has no platform, you can't pass the level with these $p$ and $k$.

You already have some level pattern $a_1$, $a_2$, $a_3$, ..., $a_n$, where $a_i = 0$ means there is no platform in the cell $i$, and $a_i = 1$ means there is one. You want to modify it so that the level can be passed with given $p$ and $k$. In $x$ seconds you can add a platform in some empty cell. In $y$ seconds you can remove the first cell completely, reducing the number of cells by one, and renumerating the other cells keeping their order. You can't do any other operation. You can not reduce the number of cells to less than $p$.

Illustration for the third example test case. Crosses mark deleted cells. Blue platform is the newly added.

What is the minimum number of seconds you need to make this level passable with given $p$ and $k$?

你正在为某款手机游戏设计一个关卡。该关卡应包含若干个从左到右排成一行的格子，格子按连续整数编号，起始编号为 $1$；每个格子中，你可以放置一个平台，也可以保持为空。

要通过该关卡，玩家需从左侧投掷一个小球，使其首次落在第 $p$ 个格子中的平台上，然后弹起，再落在第 $(p + k)$ 个格子中的平台上，接着落在第 $(p + 2k)$ 个格子中的平台上……以此类推，每次跳跃间隔 $k$ 个格子，直至小球飞出最右侧格子之外。若上述任意一个指定格子中没有平台，则无法以给定的 $p$ 和 $k$ 通过该关卡。

你已有一个初始关卡模式 $a_1$, $a_2$, $a_3$, ..., $a_n$，其中 $a_i = 0$ 表示第 $i$ 个格子中无平台，$a_i = 1$ 表示有平台。你希望修改该模式，使得关卡能以给定的 $p$ 和 $k$ 通过。你可以在某个空格子中添加一个平台，耗时 $x$ 秒；或者将最左侧的格子完全移除（即总格子数减 $1$），并对剩余格子保持原有顺序重新编号，耗时 $y$ 秒。除此之外，不允许进行其他任何操作。注意：格子总数不能减少至少于 $p$ 个。

第三个样例测试用例的示意图。叉号标记被删除的格子。蓝色平台为新添加的平台。

请问：使该关卡能以给定的 $p$ 和 $k$ 通过所需的最少秒数是多少？

The first line contains the number of test cases $t$ ($1 \le t \le 100$). Description of test cases follows.

The first line of each test case contains three integers $n$, $p$, and $k$ ($1 \le p \le n \le 10^5$, $1 \le k \le n$) — the number of cells you have, the first cell that should contain a platform, and the period of ball bouncing required.

The second line of each test case contains a string $a_1 a_2 a_3 \ldots a_n$ ($a_i = 0$ or $a_i = 1$) — the initial pattern written without spaces.

The last line of each test case contains two integers $x$ and $y$ ($1 \le x, y \le 10^4$) — the time required to add a platform and to remove the first cell correspondingly.

The sum of $n$ over test cases does not exceed $10^5$.

第一行包含测试用例的数量 $t$（$1 \le t \le 100$）。随后是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$p$ 和 $k$（$1 \le p \le n \le 10^5$，$1 \le k \le n$）——分别表示你拥有的格子数量、首个应放置平台的格子编号，以及小球弹跳所需满足的周期。

每个测试用例的第二行包含一个字符串 $a_1 a_2 a_3 \ldots a_n$（其中每个 $a_i = 0$ 或 $a_i = 1$）——即初始模式，中间无空格。

每个测试用例的最后一行包含两个整数 $x$ 和 $y$（$1 \le x, y \le 10^4$）——分别表示添加一个平台所需的时间，以及移除第一个格子所需的时间。

所有测试用例中 $n$ 的总和不超过 $10^5$。

For each test case output a single integer — the minimum number of seconds you need to modify the level accordingly.

It can be shown that it is always possible to make the level passable.

对于每个测试用例，输出一个整数——即按要求修改关卡所需的最少秒数。

可以证明，关卡总是能够被修改为可通关的。

In the first test case it's best to just remove the first cell, after that all required platforms are in their places: 0101010101. The stroked out digit is removed, the bold ones are where platforms should be located. The time required is $y = 2$.

In the second test case it's best to add a platform to both cells $4$ and $5$: 00000 $\to$ 00011. The time required is $x \cdot 2 = 4$.

In the third test case it's best to to remove the first cell twice and then add a platform to the cell which was initially $10$-th: 10110011000 $\to$ 10110011010. The time required is $y \cdot 2 + x = 10$.

在第一个测试用例中，最优策略是直接移除第一个格子，之后所有必需的平台都处于正确位置：0101010101。被划掉的数字表示被移除的格子，加粗的数字表示平台应所在的位置。所需时间为 $y = 2$。

在第二个测试用例中，最优策略是在第 $4$ 和第 $5$ 个格子均添加一个平台：00000 $\to$ 00011。所需时间为 $x \cdot 2 = 4$。

在第三个测试用例中，最优策略是两次移除第一个格子，然后在初始时为第 $10$ 个的格子上添加一个平台：10110011000 $\to$ 10110011010。所需时间为 $y \cdot 2 + x = 10$。