JJ has a binary string S of length N. JJ can perform the following operation on S:
Select an i such that 1 ≤ i ≤ 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 (i, j) in S is called an inversion if i < j 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 0s and 1s only.

------ Output Format ------ 

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

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$0 ≤ K ≤ 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 1 ------ 
Test case 1: We are allowed to perform at most $3$ operations. We can perform the following operation on $S$: $0001\underline{0}111 \rightarrow 00011111$ which has $0$ inversions. Therefore $0$ is the answer.

Test case 2: We can perform the following operation on $S$: $\underline{1}0100 \rightarrow 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\underline{0}0 \rightarrow 11101\underline{0} \rightarrow 111011$ which has $3$ inversions. It can be proven that this is the minimum number of inversions possible.

Difficulty: VERY_HARD
Tags: String algorithms

Data structures

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	s = input()
	zs = [0]
	os = [0]
	for c in s:
		if c == '1':
			zs.append(zs[-1])
			os.append(os[-1] + 1)
		else:
			zs.append(zs[-1] + 1)
			os.append(os[-1])
	tzs = zs[-1]
	tos = os[-1]
	zr = []
	ol = []
	for i in range(n):
		if s[i] == '1':
			v = tzs - zs[i + 1]
			if v == 0:
				break
			else:
				zr.append(v)
	for i in range(n - 1, -1, -1):
		if s[i] == '0':
			v = os[i + 1]
			if v == 0:
				break
			else:
				ol.append(v)
	if k >= len(zr) or k >= len(ol):
		print(0)
		continue
	a1 = [0]
	for kk in zr:
		a1.append(a1[-1] + kk)
	a2 = [0]
	for kk in ol:
		a2.append(a2[-1] + kk)
	mv = float('inf')
	diff = sum(zr)
	for i in range(k + 1):
		j = k - i
		mv = min(mv, diff - a1[i] - a2[j] + i * j)
	print(max(0, mv))


tl = int(input())
while tl:
	tl -= 1
	(n, k) = map(int, input().split())
	a = str(input())
	c0 = 0
	c1 = 0
	a0 = []
	a1 = []
	for i in a:
		if i == '0':
			c0 += 1
		else:
			c1 += 1
	ans = 0
	temp = c0
	for i in a:
		if i == '1':
			ans += temp
			a1.append(temp)
		else:
			temp -= 1
	temp1 = c1
	for i in reversed(a):
		if i == '0':
			a0.append(temp1)
		else:
			temp1 -= 1
	if k >= min(len(a0), len(a1)):
		print(0)
	else:
		f = 0
		for i in range(k):
			f += a0[i]
		fans = ans - f
		for i in range(k):
			f += a1[i] - a0[k - i - 1] + (i - (k - i - 1))
			fans = min(fans, ans - f)
		if fans < 0:
			print(0)
		else:
			print(fans)


from collections import Counter

def cis(s):
	z = 0
	ans = 0
	for i in reversed(range(len(s))):
		if s[i] == '0':
			z += 1
		else:
			ans += z
	return ans
t = int(input())
while t:
	t -= 1
	x = list(map(int, input().split()))
	a = input()
	ze = 0
	ti = ma = cis(a)
	z = []
	o = []
	for i in range(x[0]):
		if a[i] == '1':
			ze += 1
		elif ze:
			z.insert(0, ze)
	ze = 0
	for i in reversed(range(x[0])):
		if a[i] == '0':
			ze += 1
		elif ze:
			o.insert(0, ze)
	su = 0
	for i in range(len(o)):
		su += o[i]
		o[i] = su
	su = 0
	for i in range(len(z)):
		su += z[i]
		z[i] = su
	if min(len(o), len(z)) <= x[1]:
		print('0')
	elif x[1] == 1:
		ma = min(ti, ti - o[x[1] - 1])
		ma = min(ma, ti - z[x[1] - 1])
		print(ma)
	elif x[1] == 0:
		print(ti)
	else:
		ma = min(ti, ti - o[x[1] - 1])
		ma = min(ma, ti - z[x[1] - 1])
		for i in range(x[1] - 1):
			ans = ti - o[i] - z[x[1] - i - 2] + max(i + 1, x[1] - i - 1) * min(i + 1, x[1] - i - 1)
			ma = min(ans, ma)
		print(ma)


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	S = list(input())
	(l, r) = (0, N - 1)
	while l < r and S[l] == '0':
		l += 1
	while l < r and S[r] == '1':
		r -= 1
	A = []
	z = 0
	s = 0
	for i in range(r, l - 1, -1):
		if S[i] == '0':
			z += 1
		else:
			A.append((i, z))
			s += z
	A = A[::-1][:K]
	o = r - l + 1 - z
	if K >= o or K >= z:
		print(0)
		continue
	for i in A:
		s -= i[1]
		o -= 1
	ans = s
	t = 0
	while K:
		if S[r] == '0':
			(i, k) = A.pop()
			s += k - t
			o += 1
			s -= o
			K -= 1
			t += 1
		else:
			o -= 1
		ans = min(ans, s)
		r -= 1
	print(ans)


t = int(input())
for _ in range(t):
	line = input()
	nk = list(map(int, line.split()))
	n = nk[0]
	k = nk[1]
	s = list(input())
	i = 0
	Zero_values = []
	curr_value = 0
	for item in s:
		if item == '0':
			Zero_values.append(curr_value)
		else:
			curr_value += 1
	Ones_values = []
	curr_value = 0
	for i in range(n - 1, -1, -1):
		if s[i] == '1':
			Ones_values.append(curr_value)
		else:
			curr_value += 1
	Zero_values.sort(reverse=True)
	Ones_values.sort(reverse=True)
	if len(Zero_values) <= k or len(Ones_values) <= k:
		print(0)
	else:
		final_values = [sum(Zero_values[0:k])]
		pure_sums = [final_values[0]]
		for i in range(1, k + 1):
			new_value = pure_sums[i - 1] - Zero_values[k - i] + Ones_values[i - 1]
			pure_sums.append(new_value)
			new_value -= i * (k - i)
			final_values.append(new_value)
		print(sum(Zero_values) - max(final_values))