B. Toggling Flips
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Donkey has a binary string $$$s$$$ of length $$$n$$$ (each $$$s_i \in \{0,1\}$$$). Positions are indexed from $$$0$$$ to $$$n-1$$$. He also has an energy limit $$$E$$$, an integer $$$k$$$, and an integer $$$m$$$.

Donkey starts at position $$$p = 0$$$ and may perform the following actions in any order:

  • Move: choose any position $$$q$$$ ($$$0 \le q \le n-1$$$) and move from $$$p$$$ to $$$q$$$. This costs $$$|p-q|$$$ energy, and then $$$p$$$ becomes $$$q$$$.
  • Toggle: if $$$p+k \lt n$$$, he may toggle both $$$s_p$$$ and $$$s_{p+k}$$$. If the value to be toggled was $$$0$$$, it becomes $$$1$$$. If it was $$$1$$$, it becomes $$$0$$$. This action costs $$$m$$$ energy. (If $$$p+k \gt = n$$$, this action is illegal.)

The total energy spent on all actions (including both moves and toggles) must not exceed $$$E$$$.

Your task is to determine the maximum possible number of ones in the array after performing any sequence of actions within the energy limit.

Input

The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 2000$$$) — the number of test cases.

Each test case consists of:

  • a line containing four integers $$$n$$$, $$$k$$$, $$$E$$$, and $$$m$$$ $$$(1 \le n \le 500,\ 1 \le k \lt n,\ 0 \le E \le 10^{18},\ 0 \le m \le 10^{18})$$$;
  • a line containing a binary string $$$s$$$ of length $$$n$$$.

It is guaranteed that $$$\left\lfloor \frac{n}{k} \right\rfloor \le 50$$$.

The sum of $$$n$$$ over all test cases will not exceed $$$1000$$$.

Output

For each test case, output a single integer — the maximum possible number of ones in the string after operations with total energy at most $$$E$$$.

Examples
Input
3
5 2 3 1
00000
6 3 2 0
000000
5 2 2 1
10101
Output
4
6
5
Input
6
5 1 10 2
01010
5 2 10 3
00000
5 2 3 5
11111
6 2 100 0
010101
2 1 100 5
00
8 3 7 2
10100101
Output
4
4
5
5
2
8
Note

For the first test case, one optimal sequence is: toggle at $$$p=0$$$ (cost $$$1$$$), move to $$$p=1$$$ (cost $$$1$$$), then toggle at $$$p=1$$$ (cost $$$1$$$). The array changes

$$$$$$00000 \to 10100 \to 11110,$$$$$$
so the maximum number of ones is $$$4$$$.

For the second test case, $$$m=0$$$, so toggles are free and only movement matters. We can toggle at $$$p=0,1,2$$$ with total movement cost $$$2$$$, which turns all positions into $$$1$$$, so the answer is $$$6$$$.

For the third test case, move to $$$p=1$$$ (cost $$$1$$$) and toggle there (cost $$$1$$$). This flips $$$a_1$$$ and $$$a_3$$$ from $$$0$$$ to $$$1$$$, so

$$$$$$10101 \to 11111,$$$$$$
and the answer is $$$5$$$.