## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Flip to Invert Solution CodeChef | CodeChef Problem Solution 2022

JJ has a binary string $S$ of length $N$. JJ can perform the following operation on $S$:

• Select an $i$ such that $1\le i\le N$, and flip ${S}_{i}$ (i.e. change $0$ to $1$ and $1$ to $0$)

JJ wants to minimize the number of inversions in $S$ by performing the above operation at most $K$ times. Can you help JJ do so?

Recall that a pair of indices $\left(i,j\right)$ in $S$ is called an inversion if $i and ${S}_{i}>{S}_{j}$.

### Input Format

• The first line contains a single integer $T$ - the number of test cases. Then the test cases follow.
• The first line of each test case contains two integers $N$ and $K$ - the length of the binary string $S$ and the maximum number of times JJ can perform the given operation.
• The second line of each test case contains a binary string $S$ of length $N$ containing $0$s and $1$s only.

Solution Click Below:-

### Output Format

For each test case, output the minimum number of inversions possible after performing the given operation at most $K$ times.

### Constraints

• $1\le T\le {10}^{5}$
• $1\le N\le {10}^{5}$
• $0\le K\le N$
• Sum of $N$ over all test cases does not exceed $2\cdot {10}^{5}$

### Sample Input 1

3
8 3
00010111
5 1
10100
6 2
111000


### Sample Output 1

0
2
3


### Explanation

Test case 1: We are allowed to perform at most $3$ operations. We can perform the following operation on $S$$0001\underset{_}{0}111\to 00011111$ which has $0$ inversions. Therefore $0$ is the answer.

Test case 2: We can perform the following operation on $S$$\underset{_}{1}0100\to 00100$ which has $2$ inversions. It can be proven that this is the minimum number of inversions possible.

Test case 3: We can perform the following operations on $S$$1110\underset{_}{0}0\to 11101\underset{_}{0}\to 111011$ which has $3$ inversions. It can be proven that this is the minimum number of inversions possible.