您正在为某些手机游戏创建游戏关卡。该关卡应包含一定数量的单元格,从左到右排列成一行,并使用从 $$$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$$$ 秒内,您可以在某个空单元格中添加平台。在 $$$y$$$ 秒内,您可以完全删除第一个单元格,将单元格数量减少一个,并重新枚举其他单元格以保持其顺序。您无法执行任何其他操作。您无法将单元格数量减少到少于$$$p$$$。
第三个示例测试用例的插图。叉号标记已删除的单元格。蓝色平台是新增的。
在给定的 $$$p$$$ 和 $$$k$$$ 的情况下,要使此级别通过的最少秒数是多少?
输入
第一行包含测试用例的数量 $$$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$$$。
输出
对于每个测试用例,输出一个整数 - 您需要相应修改级别的最小秒数。
可以证明,总是可以使级别合格。
示例
输入 #1
3 10 3 2 0101010101 2 2 5 4 1 00000 2 10 11 2 3 10110011000 4 3
输出 #1
2 4 10
注意
在第一个测试用例中,最好只删除第一个单元格,之后所有必需的平台都就位:0101010101。删除了划线数字,粗体数字是平台应位于的位置。所需时间为 $$$y = 2$$$。
在第二个测试用例中,最好为 $$$4$$$ 和 $$$5$$$ 两个单元添加平台:00000 $$$\to$$$ 00011。所需时间为 $$$x \cdot 2 = 4$$$。
在第三个测试用例中,最好删除第一个单元两次,然后向最初为 $$$10$$$ 的单元添加平台:10110011000 $$$\to$$$ 10110011010。所需时间为 $$$y \cdot 2 + x = 10$$$。