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.

Difficulty: interview

Starter code:

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()

# cook your dish here
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)
    #print(l1)
    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)

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()

# cook your dish here
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]
    inp = list(map(int,input().split()))
    
    max = 0
    for i in range(k) :
        max = max + inp[i%n]
        sums = max
    for j in range(0,n):
        sums = sums - inp[j] + inp[(j+k)%n]
        if sums >max :
            max = sums
    print(max)
        
    


# cook your dish here
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))

# cook your dish here
def maxCircularSum(arr, n, k) : 
  
    # k must be greater  
    
  
    sum = 0; start = 0; end = k - 1;  
  
    # calculate the sum of first k elements.  
    for i in range(k) : 
        sum += arr[i];  
  
    ans = sum;  
  
    for i in range(k, n + k) : 
  
        # add current element to sum  
        # and subtract the first element  
        # of the previous window.  
        sum += arr[i % n] - arr[(i - k) % n];  
  
        if (sum > ans) : 
            ans = sum;  
            start = (i - k + 1) % n;  
            end = i % n;  
  
    return ans 
# cook your dish here
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)
    #st=wsum-a[k-1]+a[-1]
    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]
            #print(wsum)
        
        msum=max(wsum,msum)
    print(msum)
  
    


# cook your dish here
for _ 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)

# cook your dish here
for _ in range(int(input())):
    n,k=map(int,input().split())
    li=[int(x) for x in input().split()]
    
    ''''en=li[-1]
    new=li[:len(li)-1]
    ma=new[0]+new[1]
    for i in range(1,len(new)-1):
        if(new[i]+new[i+1]>ma):
            ma=new[i]+new[i+1]
        
    #new.sort(reverse=True)
    print(en+ma)'''
    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
    #print(l)
    c=sum(l[0:k])
    d=sum(l[0:k])
    for i in range(k,len(l)):
        #print(d)
        #print(i,l[i-k],l[i])
        d=(d-l[i-k])+l[i]
        c=max(c,d)
    print(c)


# cook your dish here
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)
    #print(length)
    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))

# cook your dish here
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)

# cook your dish her
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)