H. Light Ring
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ lights in a circle, numbered from $$$1$$$ to $$$n$$$ clockwise. Light $$$i$$$ initially has state $$$a_i$$$: 0 means off and 1 means on.

In one operation, choose a starting light $$$i$$$, pay $$$c_i$$$, and toggle exactly $$$k$$$ consecutive lights clockwise starting from it. Toggling changes 0 to 1 and 1 to 0; light $$$n$$$ is followed by light $$$1$$$. Any number of operations, including zero, is allowed.

Find the minimum total cost to turn all lights off.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \le T \le 10000$$$). Description of the test cases follows.

The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le k \le n \le 2 \cdot 10^5$$$).

The second line contains a binary string $$$a$$$ of length $$$n$$$. Its $$$i$$$-th character is the initial state of light $$$i$$$.

The third line contains $$$n$$$ integers $$$c_1,c_2,\ldots,c_n$$$ ($$$1 \le c_i \le 10^9$$$), giving the operation cost for each starting position.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output one line containing the answer.

Print one integer: the minimum total cost to turn all lights off.

If there is no solution, print a single integer $$$-1$$$.

Example
Input
4
5 2
00110
9 4 7 1 8
4 2
1000
1 1 1 1
6 2
110000
100 1 1 1 1 1
1 1
0
1000000000
Output
7
-1
5
0
Note

In the first test case, starting at light $$$3$$$ toggles lights $$$3$$$ and $$$4$$$ and costs $$$7$$$.

In the second test case, each operation toggles $$$2$$$ lights, so the parity of the number of lights that are on does not change. Initially, $$$1$$$ light is on, so it is impossible to turn all lights off.

In the third test case, operating once from each of lights $$$2,3,4,5,6$$$ costs $$$5$$$, whereas operating from light $$$1$$$ costs $$$100$$$.

In the fourth test case, the only light is initially off. No operations are needed, so the minimum cost is $$$0$$$.