{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eYou\u0027re 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.\u003c/p\u003e\u003cp\u003eIn 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\u0027t pass the level with these $$$p$$$ and $$$k$$$.\u003c/p\u003e\u003cp\u003eYou already have some level pattern $$$a_1$$$, $$$a_2$$$, $$$a_3$$$, ..., $$$a_n$$$, where $$$a_i \u003d 0$$$ means there is no platform in the cell $$$i$$$, and $$$a_i \u003d 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\u0027t do any other operation. You \u003cspan class\u003d\"tex-font-style-bf\"\u003ecan not\u003c/span\u003e reduce the number of cells to less than $$$p$$$.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" height\u003d\"113px\" src\u003d\"CDN_BASE_URL/028953a2e1ea641dce9a3ac1412201ca?v\u003d1715365253\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"454px\"\u003e \u003cspan class\u003d\"tex-font-size-small\"\u003eIllustration for the third example test case. Crosses mark deleted cells. Blue platform is the newly added.\u003c/span\u003e \u003c/center\u003e\u003cp\u003eWhat is the minimum number of seconds you need to make this level passable with given $$$p$$$ and $$$k$$$?\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains the number of test cases $$$t$$$ ($$$1 \\le t \\le 100$$$). Description of test cases follows.\u003c/p\u003e\u003cp\u003eThe 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$$$)\u0026nbsp;— the number of cells you have, the first cell that should contain a platform, and the period of ball bouncing required.\u003c/p\u003e\u003cp\u003eThe second line of each test case contains a string $$$a_1 a_2 a_3 \\ldots a_n$$$ ($$$a_i \u003d 0$$$ or $$$a_i \u003d 1$$$)\u0026nbsp;— the initial pattern written \u003cspan class\u003d\"tex-font-style-bf\"\u003ewithout spaces\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eThe last line of each test case contains two integers $$$x$$$ and $$$y$$$ ($$$1 \\le x, y \\le 10^4$$$)\u0026nbsp;— the time required to add a platform and to remove the first cell correspondingly.\u003c/p\u003e\u003cp\u003eThe sum of $$$n$$$ over test cases does not exceed $$$10^5$$$.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eFor each test case output a single integer\u0026nbsp;— the minimum number of seconds you need to modify the level accordingly.\u003c/p\u003e\u003cp\u003eIt can be shown that it is always possible to make the level passable.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n10 3 2\n0101010101\n2 2\n5 4 1\n00000\n2 10\n11 2 3\n10110011000\n4 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n4\n10\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn the first test case it\u0027s best to just remove the first cell, after that all required platforms are in their places: \u003cspan class\u003d\"tex-font-style-tt\"\u003e\u003cspan class\u003d\"tex-font-style-striked\"\u003e0\u003c/span\u003e10\u003cspan class\u003d\"tex-font-style-bf\"\u003e1\u003c/span\u003e0\u003cspan class\u003d\"tex-font-style-bf\"\u003e1\u003c/span\u003e0\u003cspan class\u003d\"tex-font-style-bf\"\u003e1\u003c/span\u003e0\u003cspan class\u003d\"tex-font-style-bf\"\u003e1\u003c/span\u003e\u003c/span\u003e. The stroked out digit is removed, the bold ones are where platforms should be located. The time required is $$$y \u003d 2$$$.\u003c/p\u003e\u003cp\u003eIn the second test case it\u0027s best to add a platform to both cells $$$4$$$ and $$$5$$$: \u003cspan class\u003d\"tex-font-style-tt\"\u003e000\u003cspan class\u003d\"tex-font-style-bf\"\u003e00\u003c/span\u003e\u003c/span\u003e $$$\\to$$$ \u003cspan class\u003d\"tex-font-style-tt\"\u003e000\u003cspan class\u003d\"tex-font-style-bf\"\u003e11\u003c/span\u003e\u003c/span\u003e. The time required is $$$x \\cdot 2 \u003d 4$$$.\u003c/p\u003e\u003cp\u003eIn the third test case it\u0027s best to to remove the first cell twice and then add a platform to the cell which was initially $$$10$$$-th: \u003cspan class\u003d\"tex-font-style-tt\"\u003e\u003cspan class\u003d\"tex-font-style-striked\"\u003e10\u003c/span\u003e1\u003cspan class\u003d\"tex-font-style-bf\"\u003e1\u003c/span\u003e00\u003cspan class\u003d\"tex-font-style-bf\"\u003e1\u003c/span\u003e10\u003cspan class\u003d\"tex-font-style-bf\"\u003e0\u003c/span\u003e0\u003c/span\u003e $$$\\to$$$ \u003cspan class\u003d\"tex-font-style-tt\"\u003e\u003cspan class\u003d\"tex-font-style-striked\"\u003e10\u003c/span\u003e1\u003cspan class\u003d\"tex-font-style-bf\"\u003e1\u003c/span\u003e00\u003cspan class\u003d\"tex-font-style-bf\"\u003e1\u003c/span\u003e10\u003cspan class\u003d\"tex-font-style-bf\"\u003e1\u003c/span\u003e0\u003c/span\u003e. The time required is $$$y \\cdot 2 + x \u003d 10$$$.\u003c/p\u003e"}}]}