Person in Charge

• 035966_L3

Attention

The sample cases for this problem are not placed in subtask 0. Instead, they are located elsewhere:

Sample 1 will be judged twice.

The subtask dependencies are as follows:

File I/O is required (ricecake.in / ricecake.out).

Problem Background

One evening, Sleeping Goose bought a skewer of rice cakes coated with chili sauce.

Problem Description

The bamboo skewer has $n$ positions for rice cakes, some of which are occupied (immovable) and some of which are empty.

Sleeping Goose wants to eat every rice cake in some order while minimizing the amount of chili sauce rubbed off.
When it decides to eat a rice cake, its beak touches all other rice cakes within at most $k$ positions of the chosen one.
Each time a rice cake is touched, $1$ unit of sauce is removed.

Compute the minimum total units of sauce that will be rubbed off under the best possible eating order.

Input Format

Multiple test cases.
First line: an integer $T$, the number of test cases.
For each test case:

• First line: two integers $n, k$.
• Second line: a 01-string $S$ of length $n$, where 1 indicates a rice cake at that position and 0 indicates no cake.

Output Format

For each test case, output one integer: the minimum total units of sauce rubbed off.

Samples

2
1 0
1
7 6
0000000

0
0

2
9 1
111010111
32 12
00110000100000000001000000110110

4
14

Sample 2 Explanation

For the first test case, an optimal eating order is:

1. Eat the cake at position 5.
2. Eat the cake at position 3; this touches the cake at position 2.
3. Eat the cake at position 2; this touches the cake at position 1.
4. Eat the cake at position 1.
5. Eat the cake at position 8; this touches cakes at positions 7 and 9.
6. Eat the cake at position 9.
7. Eat the cake at position 7.

Data Range

For $100\%$ of the data: $1 \le T \le 100$, $1 \le n \le 10^5$, $0 \le k \le n − 1$.

There are four equally-weighted subtasks:

1. $n \le 6$.
2. $n \le 100$.
3. Guaranteed $k = n − 1$.
4. No additional constraints.