Dexter, being irritated by DD, gave her a lucrative game to play to keep her busy.
There are $N$ bags numbered $1$ to $N$. The $i_{th}$ bag contains $A_i$ coins. The bags are placed in a circular order such that the $N_{th}$ bag is adjacent to the $1^{st}$ bag. 
DD can select $K$ consecutive adjacent bags and take all the coins in them.   Help her find the maximum number of coins she can take by making the ideal choice.
Note that the selected bags must be consecutive. Since they are placed in circular order, bag number $1$ and $N$ are considered to be consecutive.

-----Input:-----
- First-line will contain $T$, the number of test cases. Then the test cases follow. 
- First-line contains $N$ and $K$.
- Second-line contains $N$ numbers $A_1, A_2,...,A_N$,  

-----Output:-----
For each test case, output in a single line, the maximum money that can be collected by DD.

-----Constraints-----
- $1 \leq T \leq 100$
- $5 \leq N \leq 10^5$
- $1 \leq K < N$
- $1 \leq A_i \leq 10^5$
Sum of $N$ over all test cases is less than $10^6$

-----Sample Input:-----
1
5 3
8 6 9 4 10

-----Sample Output:-----
24

-----EXPLANATION:-----
The ideal choice would be to take the last bag with $10$ coins and the first $2$ bags with $8$ and $6$ coins.

Source: codechef | Difficulty: UNKNOWN_DIFFICULTY


Solutions:
t = int(input())
for i in range(t):
	(n, k) = list(map(int, input().split(' ')))
	arr = list(map(int, input().strip().split(' ')))[:n]

	def maxCircularSum(arr, n, k):
		if n < k:
			print('Invalid')
			return
		sum = 0
		start = 0
		end = k - 1
		for i in range(k):
			sum += arr[i]
		ans = sum
		for i in range(k, n + k):
			sum += arr[i % n] - arr[(i - k) % n]
			if sum > ans:
				ans = sum
				start = (i - k + 1) % n
				end = i % n
		print(ans)

	def __starting_point():
		maxCircularSum(arr, n, k)
__starting_point()


inp = list(map(int, input().split()))
t = inp[0]
for te in range(t):
	inp = list(map(int, input().split()))
	n = inp[0]
	k = inp[1]
	inpp = list(map(int, input().split()))
	max = 0
	for i in range(k):
		max = max + inpp[i % n]
		summ = max
	for j in range(0, n):
		summ = summ - inpp[j] + inpp[(j + k) % n]
		if summ > max:
			max = summ
	print(max)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	temp = list(map(int, input().split()))
	if n == k:
		print(sum(temp))
	elif n > k:
		l = len(temp)
		res = sum(temp[:k])
		s = sum(temp[:k])
		temp = temp[:] + temp[:k - 1]
		for i in range(l - 1):
			s = s - temp[i] + temp[k + i]
			if res < s:
				res = s
		print(res)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = []
	for i in range(k):
		l1.append(l[-1 - i])
	l1.reverse()
	for i in l:
		l1.append(i)
	sums = sum(l1[:k])
	sumlist = [sums]
	for i in range(len(l1) - k):
		sumlist.append(sums - l1[i] + l1[i + k])
		sums = sums - l1[i] + l1[i + k]
	print(max(sumlist))


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	s = sum(a[0:k])
	x = s
	for i in range(n - 1):
		s = s - a[i] + a[(i + k) % n]
		if x < s:
			x = s
	print(x)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	x = list(map(int, input().split()))
	x = x[-k:] + x
	y = sum(x[0:k])
	z = sum(x[0:k])
	for i in range(k, len(x)):
		z = z - x[i - k] + x[i]
		y = max(y, z)
	print(y)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	a = a + a[:k]
	s = sum(a[:k])
	maxsum = s
	for i in range(k, len(a)):
		s = s + a[i] - a[i - k]
		maxsum = max(maxsum, s)
	print(maxsum)


def maxSum(arr, n, k):
	total = sum(arr[:k])
	x = total
	for i in range(k, n):
		x += arr[i] - arr[i - k]
		total = max(total, x)
	return total
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = [int(i) for i in input().split()] * 2
	print(maxSum(li, 2 * n, k))


def maxCircularSum(arr, n, k):
	sum = 0
	start = 0
	end = k - 1
	for i in range(k):
		sum += arr[i]
	ans = sum
	for i in range(k, n + k):
		sum += arr[i % n] - arr[(i - k) % n]
		if sum > ans:
			ans = sum
			start = (i - k + 1) % n
			end = i % n
	return ans
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	print(maxCircularSum(l, n, k))


def maxCircularSum(arr, n, k):
	sum = 0
	start = 0
	end = k - 1
	for i in range(k):
		sum += arr[i]
	ans = sum
	for i in range(k, n + k):
		sum += arr[i % n] - arr[(i - k) % n]
		if sum > ans:
			ans = sum
			start = (i - k + 1) % n
			end = i % n
	print(ans)
t = int(input())
for i in range(t):
	lst1 = input().split()
	n = int(lst1[0])
	k = int(lst1[1])
	lst = input().split()
	lst = [int(l) for l in lst]
	maxCircularSum(lst, n, k)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = a[0:k]
	a.extend(b)
	i = 0
	s = sum(a[i:i + k])
	i = k
	temp = s
	while i < n + k - 1:
		temp = temp + a[i] - a[i - k]
		if temp > s:
			s = temp
		i += 1
	print(s)


for i in range(int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	s = 0
	s = sum(li[0:k])
	m = s
	for i in range(n - 1):
		if k + i >= n:
			s = s - li[i] + li[k + i - n]
		else:
			s = s - li[i] + li[k + i]
		if s > m:
			m = s
	print(m)


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = [int(i) for i in input().split()]
	wsum = 0
	msum = 0
	for i in range(k):
		wsum += a[i]
	msum = max(wsum, msum)
	for i in range(k, n + k - 1):
		if i < n:
			wsum += a[i] - a[i - k]
		else:
			wsum += a[abs(n - i)] - a[i - k]
		msum = max(wsum, msum)
	print(msum)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	li = [int(x) for x in input().split()]
	su = 0
	st = 0
	end = k - 1
	for i in range(k):
		su += li[i]
	res = su
	for i in range(k, n + k):
		su += li[i % n] - li[(i - k) % n]
		if su > res:
			res = su
	print(res)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	l = l[-k:] + l
	c = sum(l[0:k])
	d = sum(l[0:k])
	for i in range(k, len(l)):
		d = d - l[i - k] + l[i]
		c = max(c, d)
	print(c)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split(' ')))
	s = input().split(' ')
	try:
		a = list(map(int, s))
	except:
		a = list(map(int, s[:-1]))
	out = -1
	dp = [a[0]]
	for i in range(1, k):
		dp.append(dp[-1] + a[i])
		out = max(out, dp[-1])
	i = k
	visited = False
	while True:
		dp.append(dp[-1] - a[(i - k) % n] + a[i])
		out = max(out, dp[-1])
		if i == n - 1:
			if not visited:
				visited = True
			else:
				break
		i = (i + 1) % n
	print(out)


t = int(input())
while t:
	(n, k) = input().split()
	(n, k) = (int(n), int(k))
	a = [int(i) for i in input().split()]
	b = a[:k - 1]
	a = a + b
	max = sum(a[:k])
	temp = max
	for i in range(1, n):
		temp = temp - a[i - 1] + a[i + k - 1]
		if temp > max:
			max = temp
	print(max)
	t -= 1


try:

	def maxSum(arr, n, k):
		res = 0
		for i in range(k):
			res += arr[i]
		curr_sum = res
		for i in range(k, n):
			curr_sum += arr[i] - arr[i - k]
			res = max(res, curr_sum)
		return res
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		arr = list(map(int, input().split()))
		arr = arr + arr[:k - 1]
		n1 = len(arr)
		print(maxSum(arr, n1, k))
except:
	pass


t = int(input())
for i in range(t):
	(n, k) = input().split()
	k = int(k)
	n = int(n)
	l = [int(x) for x in input().split()]
	for i in range(k - 1):
		l.append(l[i])
	length = len(l)
	sum = 0
	for i in range(k):
		sum += l[i]
	max = sum
	end = k - 1
	start = 0
	while end != length:
		if sum > max:
			max = sum
		end += 1
		if end <= length - 1:
			sum += l[end]
		sum -= l[start]
		start += 1
	print(max)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	if k > 1:
		for i in range(k - 1):
			l.append(l[i])
	p = []
	p.append(l[0])
	for i in range(1, len(l)):
		p.append(p[i - 1] + l[i])
	j = 0
	sub = 0
	for i in range(k, len(l)):
		sub += l[j]
		j += 1
		p[i] -= sub
	print(max(p))


for k in range(int(input())):
	(num, bags) = map(int, input().split())
	coins = list(map(int, input().split()))
	most = 0
	temp = sum(coins[:bags])
	for i in range(num):
		if i + bags <= num:
			temp = temp - coins[i] + coins[(i + bags) % num]
		else:
			temp = temp - coins[i] + coins[(i + bags) % num]
		if temp > most:
			most = temp
	print(most)


for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))

	def ki(v, n, k):
		if n < k:
			print(0)
		su = 0
		a = 0
		e = k - 1
		for i in range(k):
			su += v[i]
		for i in range(k, n + k):
			su += v[i % n] - v[(i - k) % n]
			if su > a:
				a = su
		print(a)
	ki(l, n, k)