Read problems statements in [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

You are given a positive integer $K$ and a sequence $A_{1}, A_{2}, \ldots, A_{N}$. Initially, each element of this sequence is $0$ or $1$; your goal is to make all elements equal to $0$.

In order to do that, you may perform the following operation any number of times:
Choose a subarray (a contiguous subsequence) with length $K$, i.e. choose two indices $L$ and $R$ such that $1 ≤ L ≤ R ≤ N$ and $R-L+1 = K$.
Choose one element of that subarray and change it to $0$, i.e. choose an index $P$ such that $L ≤ P ≤ R$ and change $A_{P}$ to $0$.
The cost of this operation is the sum of this subarray $A_{L} + A_{L+1} + \ldots + A_{R}$ before $A_{P}$ is changed.

Find the minimum total cost (sum of costs of individual operations) of making all elements of $A$ equal to $0$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains two space-separated integers $N$ and $K$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \ldots, A_{N}$.

------  Output ------
For each test case, print a single line containing one integer ― the minimum cost of turning all elements of $A$ into zeros. 

------  Constraints ------
$1 ≤ T ≤ 200$
$1 ≤ K ≤ N ≤ 2 \cdot 10^{5}$
$0 ≤ A_{i} ≤ 1$ for each valid $i$
the sum of $N$ over all test cases does not exceed $4 \cdot 10^{5}$

----- Sample Input 1 ------ 
3

5 3

1 0 1 0 1

4 4

1 1 0 1

3 1

1 1 0
----- Sample Output 1 ------ 
3

6

2
----- explanation 1 ------ 
Example case 1: The minimum cost is $3$ and it can be obtained using the following sequence of operations:
- choose the subarray $[L,R] = [2,4]$ and set $A_{3}=0$ with cost $1$
- choose the subarray $[1,3]$ and set $A_{1}=0$ with cost $1$
- choose the subarray $[3,5]$ and set $A_{5}=0$ with cost $1$

Example case 2: We have to choose the whole sequence ($[L,R] = [1,4]$) in each operation, so the total cost is $3+2+1=6$:
- choose the subarray $[1,4]$ and set $A_{1}=0$ with cost $3$ 
- choose the subarray $[1,4]$ and set $A_{2}=0$ with cost $2$
- choose the subarray $[1,4]$ and set $A_{4}=0$ with cost $1$

Example case 3: The minimum cost is $2$ and it can be obtained using the following sequence of operations:
- choose the subarray $[2,2]$ and set $A_{2}=0$ with cost $1$
- choose the subarray $[1,1]$ and set $A_{1}=0$ with cost $1$

Difficulty: HARD
Tags: Combinatorics

Data structures
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	no = 0
	mn = float('inf')
	arr = [[0, 0]]
	for i in range(N):
		if A[i] == 1:
			no += 1
		x = arr[-1][:]
		x[A[i]] += 1
		arr.append(x)
		if i + 1 >= K:
			z = arr[-1][1] - arr[i - K + 1][1]
			mn = min(z, mn)
	ans = mn * (1 + mn) // 2
	no -= mn
	ans += no
	print(ans)


T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	m = k
	L = [0] * n
	for i in range(n):
		if A[i] == 1:
			if i == 0:
				L[i] = 1
			else:
				L[i] = L[i - 1] + 1
		elif i == 0:
			L[i] = 0
		else:
			L[i] = L[i - 1]
		if i < k - 1:
			pass
		elif i == k - 1:
			m = min(m, L[k - 1])
		else:
			m = min(m, L[i] - L[i - k])
	x = L[-1]
	x -= m
	ans = m * (m + 1) // 2 + x
	print(ans)


import sys
from math import sqrt, gcd, factorial, ceil, floor, pi
from collections import deque, Counter, OrderedDict
from heapq import heapify, heappush, heappop
input = lambda : sys.stdin.readline()
I = lambda : int(input())
S = lambda : input().strip()
M = lambda : map(int, input().strip().split())
L = lambda : list(map(int, input().strip().split()))
mod = 1000000007
for _ in range(I()):
	(n, k) = M()
	a = L()
	ans = float('inf')
	(i, j, c) = (0, 0, 0)
	while j < n:
		if a[j]:
			c += 1
		if j - i + 1 == k:
			ans = min(ans, c)
			if a[i]:
				c -= 1
			i += 1
		j += 1
	c = a.count(1)
	print(ans * (ans + 1) // 2 + c - ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k == 1:
		print(sum(a))
	else:
		s = sum(a)
		s1 = sum(a[:k])
		x = s1
		z = 0
		for j in range(k, n):
			s1 += a[j] - a[z]
			x = min(s1, x)
			z += 1
		ans = x * (x + 1) // 2 + s - x
		print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	data = list(map(int, input().split()))
	pre = [0] * (n + 1)
	for i in range(n):
		pre[i + 1] = pre[i] + data[i]
	lowest = pow(10, 10)
	for i in range(n - k + 1):
		cost = pre[i + k] - pre[i]
		lowest = min(lowest, cost)
	result = lowest * (lowest + 1) // 2
	result += sum(data) - lowest
	print(result)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	if k == 1:
		print(sum(a))
	else:
		t = sum(a)
		temp = sum(a[:k])
		x = temp
		j = 0
		for i in range(k, n):
			temp = temp + a[i] - a[j]
			x = min(temp, x)
			j += 1
		res = x * (x + 1) // 2 + t - x
		print(res)


from sys import stdin
input = stdin.readline

def answer():
	total = sum(a[:k])
	(ans, m, j) = (total, total, 0)
	for i in range(k, n):
		ans += a[i]
		total += a[i] - a[j]
		m = min(m, total)
		j += 1
	return ans + m * (m - 1) // 2
for T in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(answer())


def solve(A, N, K):
	i = 0
	num_ones = A[:K].count(1)
	min_num_ones = num_ones
	for i in range(N - K):
		num_ones -= A[i] == 1
		num_ones += A[i + K] == 1
		min_num_ones = min(num_ones, min_num_ones)
	cost_for_worst_interval = min_num_ones * (min_num_ones + 1) // 2
	return cost_for_worst_interval + A.count(1) - min_num_ones
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	print(solve(A, N, K))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	ind = [0] * (n + 1)
	for i in range(1, n + 1):
		ind[i] = ind[i - 1] + l[i - 1]
	mx = k
	for i in range(1, k + 1):
		for j in range(i, n + 1, k):
			if j + k - 1 <= n:
				mx = min(mx, ind[j + k - 1] - ind[j - 1])
	print((mx + 1) * mx // 2 + l.count(1) - mx)


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	c = a.count(1)
	an = 0
	for i in range(k):
		if a[i] == 0:
			an += 1
	j = 0
	aa = an
	for i in range(k, n):
		if a[i] == 0:
			an += 1
		if a[j] == 0:
			an -= 1
		aa = max(aa, an)
		j += 1
	if aa == k:
		print(c)
	else:
		co = k - aa
		ans = 0
		for i in range(1, co + 1):
			ans += i
			c -= 1
		print(ans + c)
	t -= 1


t = int(input())
for x in range(t):
	(n, k) = map(int, input().split())
	lst = [int(i) for i in input().split()]
	tsum = sum(lst)
	psum = sum(lst[:k])
	m = psum
	j = 0
	for i in range(k, n):
		psum = psum + lst[i] - lst[j]
		j += 1
		m = min(m, psum)
	res = m * (m + 1) // 2 + tsum - m
	print(res)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	x = 0
	cnt1 = 0
	cnt0 = 0
	for i in range(n):
		if a[i] == 1:
			cnt1 += 1
		if i >= k:
			if a[i] == 1 and a[i - k] == 0:
				cnt0 -= 1
			if a[i] == 0 and a[i - k] == 0:
				cnt0 -= 1
		if a[i] == 0:
			cnt0 += 1
			if cnt0 > x:
				x = cnt0
	y = k - x
	ans = cnt1 - y
	ans += y * (y + 1) // 2
	print(ans)


b = int(input())
for test in range(b):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = sum(a)
	res = sum(a[:k])
	m = res
	j = 0
	for i in range(k, n):
		res = res + a[i] - a[j]
		m = min(m, res)
		j = j + 1
	ans = m * (m + 1) // 2 + (s - m)
	print(ans)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	s = sum(a)
	res = sum(a[:k])
	m = res
	j = 0
	for i in range(k, n):
		res = res + a[i] - a[j]
		m = min(m, res)
		j = j + 1
	ans = m * (m + 1) // 2 + (s - m)
	print(ans)


for t in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	s = sum(A)
	ans = sum(A[:k])
	m = ans
	c = 0
	for i in range(k, n):
		ans = ans + A[i] - A[c]
		m = min(m, ans)
		c = c + 1
	res = m * (m + 1) // 2 + (s - m)
	print(res)


for _ in range(int(input())):
	(m, n) = map(int, input().split())
	arr = list(map(int, input().split()))
	mini = sum(arr[:n])
	i = 0
	win = [i, n - 1]
	temp = mini
	for j in range(n, m):
		temp = temp + arr[j] - arr[i]
		if temp < mini:
			win = [i + 1, j]
			mini = mini + arr[j] - arr[i]
		i += 1
	ans = mini * (mini + 1) // 2
	(i, j) = (win[0], win[1])
	print(ans + sum(arr[:i]) + sum(arr[j + 1:]))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	l = [0]
	for i in range(k):
		l[-1] += a[i]
	for i in range(k, n):
		l.append(l[-1] - a[i - k] + a[i])
	print(a.count(1) - min(l) + min(l) * (min(l) + 1) // 2)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = sum(l)
	res = sum(l[:k])
	l1 = res
	j = 0
	for i in range(k, n):
		res = res + l[i] - l[j]
		l1 = min(l1, res)
		j = j + 1
	a = l1 * (l1 + 1) // 2 + (s - l1)
	print(a)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = sum(arr[:k])
	i = 0
	w = [i, k - 1]
	temp = s
	for j in range(k, n):
		temp = temp + arr[j] - arr[i]
		if temp < s:
			w = [i + 1, j]
			s = s + arr[j] - arr[i]
		i += 1
	ans = s * (s + 1) // 2
	(i, j) = (w[0], w[1])
	print(ans + sum(arr[:i]) + sum(arr[j + 1:]))


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = [int(x) for x in input().split()]
	s = sum(l)
	res = sum(l[:k])
	(temp, j) = (res, 0)
	for i in range(k, n):
		res = res + l[i] - l[j]
		temp = min(temp, res)
		j = j + 1
	out = temp * (temp + 1) // 2 + (s - temp)
	print(out)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	x = list(map(int, input().split()))
	s = sum(x)
	res = sum(x[:k])
	p = res
	j = 0
	for i in range(k, n):
		res = res + x[i] - x[j]
		p = min(p, res)
		j = j + 1
	ans = p * (p + 1) // 2 + (s - p)
	print(ans)


for t in range(int(input())):
	(nu, k) = map(int, input().split())
	li = list(map(int, input().split()))
	li1 = [0]
	for i in range(len(li)):
		li1.append(li1[i] + li[i])
	x = li1[-1]
	c = 0
	temp = k
	for i in range(k, len(li1)):
		c = li1[i] - li1[i - k]
		if c < temp:
			temp = c
	total = temp / 2 * (temp + 1)
	total += x - temp
	print(int(total))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	ans = [0]
	for i in range(k):
		ans[-1] += a[i]
	for i in range(k, n):
		ans.append(ans[-1] - a[i - k] + a[i])
	x = a.count(1) - min(ans) + min(ans) * (min(ans) + 1) // 2
	print(x)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	minimum = sum(a[:k])
	i = 0
	window = [i, k - 1]
	temp = minimum
	for j in range(k, n):
		temp += a[j] - a[i]
		if temp < minimum:
			window = [i + 1, j]
			minimum += a[j] - a[i]
		i += 1
	ans = minimum * (minimum + 1) // 2
	(i, j) = (window[0], window[1])
	print(ans + sum(a[:i]) + sum(a[j + 1:]))


from sys import stdin
input = stdin.readline

def answer():
	value = 0
	for i in range(k):
		value += a[i]
	(sub, j) = (value, 0)
	for i in range(k, n):
		value += a[i] - a[j]
		j += 1
		sub = min(sub, value)
	return sub * (sub + 1) // 2 + sum(a) - sub
for T in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	print(answer())


from sys import stdin, stdout
nmbr = lambda : int(input())
lst = lambda : list(map(int, input().split()))
for _ in range(nmbr()):
	(n, k) = lst()
	a = lst()
	ones = a.count(1)
	mn = ones
	i = j = 0
	sm = 0
	while j < n:
		sm += a[j]
		if j - i + 1 < k:
			j += 1
		else:
			mn = min(mn, sm)
			sm -= a[i]
			i += 1
			j += 1
	left = ones - mn
	print(mn * (mn + 1) // 2 + left)


import sys
input = lambda : sys.stdin.readline()

def main():
	d = dict()
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		a = list(map(int, input().split()))
		l = [0]
		for i in range(k):
			l[-1] += a[i]
		for i in range(k, n):
			l.append(l[-1] - a[i - k] + a[i])
		print(a.count(1) - min(l) + min(l) * (min(l) + 1) // 2)
main()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	mi = 999999
	if n == k:
		ans = 0
		for i in range(1, sum(arr) + 1):
			ans += i
		print(ans)
	elif k == 1:
		print(sum(arr))
	else:
		ps = [0 for i in range(n)]
		ps[0] = arr[0]
		for i in range(1, n):
			ps[i] = ps[i - 1] + arr[i]
		diff = 0
		for i in range(k - 1, n):
			if ps[i] - diff < mi:
				mi = ps[i] - diff
				start = i - k + 1
				end = i
			diff = ps[i - k + 1]
		ans = 0
		for i in range(1, mi + 1):
			ans += i
		fhalf = sum(arr[:start])
		shalf = sum(arr[end + 1:])
		print(ans + fhalf + shalf)


try:
	n = int(input().strip())
	for i in range(n):
		(m1, k) = map(int, input().strip().split(' '))
		l = list(map(int, input().strip().split(' ')))
		l2 = [0]
		for i in range(len(l)):
			l2.append(l2[i] + l[i])
		total = l2[-1]
		mini = k
		one = 0
		for i in range(k, len(l2)):
			one = l2[i] - l2[i - k]
			if one < mini:
				mini = one
		cost = mini / 2 * (mini + 1)
		cost = cost + total - mini
		print(int(cost))
except:
	pass


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	map_a = {i: {} for i in range(k + 1)}
	map_b = {}
	s = sum(A[:k])
	(ms, mi) = (s, 0)
	for i in range(k, n):
		s -= A[i - k]
		s += A[i]
		if s < ms:
			mi = i - k + 1
			ms = s
	t = sum(A)
	print(t - ms + ms * (ms + 1) // 2)


T = int(input())
for i in range(T):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [sum(a[0:k])]
	for i in range(0, len(a) - k):
		b.append(b[-1] - a[i] + a[i + k])
	m = min(b)
	print(int(sum(a) + m * (m + 1) / 2 - m))


try:

	def condel(nums, k):
		total_ones = 0
		for i in range(len(nums)):
			if nums[i] == 1:
				total_ones += 1
		sum_window = 0
		for i in range(k):
			sum_window += nums[i]
		min_sum = sum_window
		for i in range(k, len(nums)):
			sum_window = sum_window + nums[i] - nums[i - k]
			min_sum = min(sum_window, min_sum)
		res = min_sum * (min_sum + 1) // 2 + (total_ones - min_sum)
		return res
	t = int(input())
	for i in range(t):
		(n, k) = [int(j) for j in input().split()]
		input_arr = [int(k) for k in input().split()]
		res = condel(input_arr, k)
		print(res)
except:
	pass


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	s = sum(l[:k])
	y = k
	i = 0
	ans = 0
	mina = s
	w = s
	a = [s]
	for i in range(n - k):
		w = w - l[i] + l[i + k]
		a.append(w)
	x = min(a)
	ans = sum(l)
	print(ans - x + x * (x + 1) // 2)


T = int(input())
for n1 in range(T):
	(n, k) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	mini = sum(l[0:k])
	m = mini
	for i in range(len(l) - k):
		mini = mini - l[i] + l[i + k]
		if mini < m:
			m = mini
	print(int(m * (m + 1) / 2 + sum(l) - m))


T = int(input())
for n1 in range(T):
	(n, k) = [int(i) for i in input().split(' ')]
	l = [int(i) for i in input().split(' ')]
	L = [sum(l[0:k])]
	for i in range(0, len(l) - k):
		L.append(L[-1] - l[i] + l[i + k])
	m = min(L)
	print(int(sum(l) + m * (m + 1) / 2 - m))


def func(n, k, arr):
	mn = 1000000
	a = 0
	ps = [0 for i in range(n + 2)]
	for i in range(n):
		ps[i + 1] = ps[i] + arr[i]
		a += arr[i]
	for i in range(1, n - k + 2):
		mn = min(ps[i + k - 1] - ps[i - 1], mn)
	return int(mn * (mn + 1) / 2) + a - mn
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	print(func(n, k, arr))


import sys
intinp = lambda : int(input())

def listinp(func=int):
	return list(map(func, input().split()))

def nsepline(n, func=str):
	return [func(input()) for _ in range(n)]

def printlist(li, glue=' '):
	return glue.join(list(map(str, li)))

def fop(s, end='\n'):
	sys.stdout.write(str(s) + end)

def fip():
	return sys.stdin.readline().strip()
fintinp = lambda : int(fip())

def flistinp(func=int):
	return list(map(func, fip().split()))

def fnsepline(n, func=str):
	return [func(fip()) for _ in range(n)]
test_cases = fintinp()
for _ in range(test_cases):
	(n, k) = flistinp()
	l = flistinp()
	pfs = [0]
	for i in l:
		pfs.append(pfs[-1] + i)
	mina = 0
	ms = int(1000000000.0)
	(a, b) = (0, k - 1)
	while b < n:
		cs = pfs[b + 1] - pfs[a]
		if cs < ms and cs > 0:
			ms = cs
			mina = a
		a += 1
		b += 1
	for i in range(mina, mina + k):
		l[i] = 0
	if ms == int(1000000000.0):
		ms = 0
	print((ms * (ms + 1) >> 1) + l.count(1))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	cs = [0]
	for i in range(1, n + 1):
		cs.append(l[i - 1] + cs[i - 1])
	minimum_ones = k
	for i in range(k, n + 1):
		subarray_ones = cs[i] - cs[i - k]
		minimum_ones = min(minimum_ones, subarray_ones)
	ans = minimum_ones * (minimum_ones + 1) // 2 + cs[n] - minimum_ones
	print(ans)


T = int(input())
ans = []
for _ in range(T):
	(N, K) = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	cost = 0
	for i in range(K):
		if A[i] == 1:
			cost += 1
	C = [cost]
	for i in range(1, N - K + 1):
		if A[i - 1] == 1:
			cost = max(cost - 1, 0)
		if A[i + K - 1] == 1:
			cost = min(cost + 1, K)
		C.append(cost)
	m = C[0]
	ind = 0
	for i in range(N - K + 1):
		if C[i] < m:
			m = C[i]
			ind = i
	cost = m * (m + 1) // 2
	for i in range(max(ind - K + 1, 0), min(ind + K - 1, N - K + 1)):
		C[i] -= m
	total = 0
	for i in range(N):
		if A[i] == 1:
			total += 1
	ans.append(total - m + cost)
for i in ans:
	print(i)


R = lambda : map(int, input().split())
(t,) = R()
for _ in range(t):
	(n, k) = R()
	v = [*R()]
	su = sum((i for i in v))
	su1 = sum((i for i in v[:k]))
	mi = su1
	for i in range(k, n):
		su1 -= v[i - k] - v[i]
		mi = min(mi, su1)
	print(mi * (mi + 1) // 2 + su - mi)


def fun(arr, n, k):
	res = 0
	for i in range(0, k):
		res += arr[i]
	csum = res
	for j in range(k, n):
		csum += arr[j] - arr[j - k]
		res = min(res, csum)
	return res
	return res
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	ha = a.count(1)
	m = fun(a, n, k)
	ha = ha - m
	ans = m * (m + 1) // 2
	ans += ha
	print(ans)


def fun(c):
	return c
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = input().split()
	o = 0
	for i in range(k):
		if a[i] == '1':
			o += 1
	m = o
	mi = (0, k - 1)
	for i in range(k, n):
		if a[i] == '1':
			o += 1
		if a[i - k] == '1':
			o -= 1
		if o < m:
			m = o
			mi = (i - k + 1, i)
	c = int(m * (m + 1) / 2)
	for i in range(mi[0]):
		if a[i] == '1':
			c += 1
	for i in range(mi[1] + 1, n):
		if a[i] == '1':
			c += 1
	print(fun(c))


import sys

def solve(arr, n, k):
	start = -sys.maxsize
	end = sys.maxsize
	prefix = [0] * n
	prefix[0] = arr[0]
	total = 0
	for i in range(len(arr)):
		if arr[i] == 1:
			total += 1
	for i in range(1, len(arr)):
		prefix[i] = prefix[i - 1] + arr[i]
	minimum = prefix[k - 1]
	for i in range(k, len(arr)):
		if prefix[i] - prefix[i - k] < minimum:
			minimum = prefix[i] - prefix[i - k]
			start = i - k + 1
			end = i
	res = minimum * (minimum + 1) // 2
	ans = res + total - minimum
	return ans
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	ans = solve(arr, n, k)
	print(ans)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	dp = [0] * (n + 1)
	for i in range(1, n + 1):
		dp[i] = dp[i - 1] + arr[i - 1]
	tot = dp[n]
	mini = k
	for i in range(k, n + 1):
		ones = dp[i] - dp[i - k]
		mini = min(ones, mini)
	cost = mini * (mini + 1) // 2 + tot - mini
	print(cost)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	sumOfk = sum(l[:k])
	minimum = sumOfk
	for i in range(k, n):
		sumOfk += l[i]
		sumOfk -= l[i - k]
		minimum = min(minimum, sumOfk)
	res = sum(l) - minimum
	answer = res + minimum * (minimum + 1) // 2
	print(answer)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	initial = sum(a[:k])
	mini = initial
	for i in range(k, n):
		initial += a[i]
		initial -= a[i - k]
		mini = min(initial, mini)
	r = mini * (mini + 1) // 2
	ans = sum(a) - mini + r
	print(ans)


import sys
input = sys.stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())

def solve():
	for _ in range(I()):
		(n, k) = R()
		a = L()
		s = sum(a[:k])
		mn = s
		for i in range(k, n):
			s = s - a[i - k] + a[i]
			mn = min(mn, s)
		rest = sum(a) - mn
		ans = mn * (mn + 1) // 2 + rest
		print(ans)
solve()


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	total = 0
	for i in a:
		if i == 1:
			total += 1
	temp = 0
	for i in range(k):
		if a[i] == 1:
			temp += 1
	minct = temp
	for i in range(n - k):
		if a[i] == 1:
			temp -= 1
		if a[i + k] == 1:
			temp += 1
		if temp < minct:
			minct = temp
	ans = minct * (minct + 1) // 2 + total - minct
	print(ans)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	if k == 1:
		print(sum(arr))
	else:
		(l, r) = (0, k)
		total = sum(arr[l:r])
		mini = total
		for i in range(1, n - k + 1):
			hey = total + arr[i + k - 1]
			hey = abs(hey - arr[i - 1])
			total = hey
			if total < mini:
				mini = total
		heyy = sum(arr) - mini
		harish = mini * (mini + 1) // 2
		print(harish + heyy)


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	l = []
	s = 0
	m = sum(a[:k])
	w = m
	c = a.count(1)
	for i in range(n - k):
		w = w - a[i] + a[k + i]
		m = min(m, w)
	print(int(m * (m + 1) / 2) + (c - m))


import sys
input = sys.stdin.readline
import math
T = int(input())
for _ in range(T):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	total_ones = sum(a)
	total = sum(a[:k])
	min_sum = total
	for i in range(k, n):
		total += a[i] - a[i - k]
		min_sum = min(min_sum, total)
	cost = total_ones - min_sum
	cost += min_sum * (min_sum + 1) // 2
	print(cost)


for t in range(int(input())):
	(N, K) = map(int, input().split())
	s = list(map(int, input().split()))
	add = sum(s[0:K])
	m = add
	for i in range(1, N - K + 1):
		add = add - s[i - 1] + s[i + K - 1]
		if add < m:
			m = add
	print(m * (m + 1) // 2 + s.count(1) - m)