You are given an array A with size N (indexed from 0) and an integer K. Let's define another array B with size N · K as the array that's formed by concatenating K copies of array A.
For example, if A = {1, 2} and K = 3, then B = {1, 2, 1, 2, 1, 2}.
You have to find the maximum subarray sum of the array B. Fomally, you should compute the maximum value of Bi + Bi+1 + Bi+2 + ... + Bj, where 0 ≤ i ≤ j < N · K.

-----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 A0, A1, ..., AN-1.

-----Output-----
For each test case, print a single line containing the maximum subarray sum of B.

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
- 1 ≤ K ≤ 105
- -106 ≤ Ai ≤ 106 for each valid i

-----Subtasks-----
Subtask #1 (18 points): N · K ≤ 105
Subtask #2 (82 points): original constraints

-----Example-----
Input:

2
2 3
1 2
3 2
1 -2 1

Output:

9
2

-----Explanation-----
Example case 1: B = {1, 2, 1, 2, 1, 2} and the subarray with maximum sum is the whole {1, 2, 1, 2, 1, 2}. Hence, the answer is 9.
Example case 2: B = {1, -2, 1, 1, -2, 1} and the subarray with maximum sum is {1, 1}. Hence, the answer is 2.

Difficulty: interview

Starter code:

Solutions:
def max_sum(arr):
    # Finds the maximum sum of sub-arrays of arr
    max_till_now = -1000000 #minimum possible number 
    current_sum = 0
    for i in range(len(arr)):
        if current_sum < 0:
            # If sum of previous elements is negative, then ignore them. Start fresh
            # with `current_sum = 0`
            current_sum = 0
        
        current_sum += arr[i]
        
        # Update max
        if max_till_now < current_sum:
            max_till_now = current_sum
    
    return max_till_now


def solve(A, k):
    if k == 1:
        return max_sum(A)
    # Find sum of elements of A
    sum_A = 0
    for i in range(len(A)):
        sum_A += A[i]
    
    Max_Suffix_Sum = -1000000
    current = 0
    for i in range(len(A)):
        current += A[-i-1]
        if current > Max_Suffix_Sum:
            Max_Suffix_Sum = current

    Max_Prefix_Sum = -1000000
    current = 0
    for i in range(len(A)):
        current += A[i]
        if current > Max_Prefix_Sum:
            Max_Prefix_Sum = current

    if sum_A <= 0:
        # Check two cases:

        # Case 1 : Check the max_sum of A
        case_1_max_sum = max_sum(A)
        
        # Case 2 : Check the max_sum of A + A
        case_2_max_sum = Max_Suffix_Sum + Max_Prefix_Sum

        # Return the maximum of the two cases
        return max([case_1_max_sum, case_2_max_sum])

    else: # if sum_A > 0
        #Check two cases:

        # Case 1 : Check the max_sum of A
        case_1_max_sum = max_sum(A)

        # Case 2
        # Max sum = Max_Suffix_Sum + (k - 2)*sum_A + Max_Prefix_Sum       
        
        case_2_max_sum = Max_Suffix_Sum + (k - 2)*sum_A + Max_Prefix_Sum
        
        # Return the maximum of the two cases
        return max([case_1_max_sum, case_2_max_sum])


# Main
T = int(input()) # No of test cases
for i in range(T):
    [N, k] = list(map(int, input().split(" ")))
    A = list(map(int, input().split(" ")))
    
    answer = solve(A,k)
    print(answer)

# cook your dish here
t=int(input())
for i in range(t):
    
    l=list(map(int,input().split()))
    l2=list(map(int,input().split()))
    if (sum(l2)>0):
        x=0
        if l[1]==1:
            h=l2
            y=0
            
            for j in range(len(h)):
                y=max(0,y+h[j])
                x=max(y,x)
            print(x)
        else:  
            h=l2+l2
            y=0
            
            for j in range(len(h)):
                y=max(0,y+h[j])
                x=max(y,x)
            print(x+(l[1]-2)*sum(l2))
            
        
        
    else:
        if max(l2)<0:
            print(max(l2))
        else:
            x=0
            if l[1]==1:
                h=l2
                y=0
                
                for j in range(len(h)):
                    y=max(0,y+h[j])
                    x=max(y,x)
                print(x)
            else:  
                h=l2+l2
                y=0
                
                for j in range(len(h)):
                    y=max(0,y+h[j])
                    x=max(y,x)
                print(x)
            
            
            


# cook your dish here
x = int(input())
for i in range(x):
    n, k = map(int, input().split())
    arr = list(map(int, input().split()))
    ar = [i for i in arr]*k
    l = [0 for i in range(n*k)]
    l[0] = ar[0]
    for i in range(n*k):
        l[i] = max([l[i-1]+ar[i], ar[i]])
    print(max(l))

def maxSumSubarray(B):          # O(N)
    import sys
    currSum, maxSum = 0, -(sys.maxsize - 1)
    for b in B:
        currSum += b
        if currSum > maxSum:
            maxSum = currSum
        if currSum < 0:
            currSum = 0
    return maxSum

def formB(A, K):
    B = [0 for _ in range(len(A) * K)]
    for i in range(len(A)):     # O(NK)
        B[i] = A[i]
        ti, j = i, 1
        while j < K:
            B[ti + len(A)] = A[i]
            ti += len(A)
            j += 1
    
    # print(B)
    return maxSumSubarray(B)
    
    
    
try:
    T = int(input())
except Exception as e:
    pass
else:
    while T >= 1:
        N, K = map(int, input().split())
        A = [int(x) for x in input().split()]
        print(formB(A, K))
        T -= 1

# cook your dish here
t = int(input())
for i in range(t):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    #print(n, k, a)
    b = [i for i in a]*k
    #print(k, a, b)
    new = [0 for i in range(n*k)]
    new[0] = b[0]
    for i in range(n*k):
        new[i] = max([new[i-1]+b[i], b[i]])
    #print(new)
    print(max(new))

# cook your dish here
def maxsubarraysum(arr):
    max_till=arr[0]
    max_cur=arr[0]
    n=len(arr)
    for i in range(1,n):
        max_cur=max(arr[i],max_cur+arr[i])
        max_till=max(max_cur,max_till)
    return max_till
    
for _ in range(int(input())):
    n,m = map(int,input().split())
    arr = [int(i) for i in input().split()]
    if m==1:
        print(maxsubarraysum(arr))
    else:
        arr2 = arr+arr
        if m==2:
            print(maxsubarraysum(arr2))
        else:
            maxsum2 = maxsubarraysum(arr2)
            if sum(arr)>=0:
                print(maxsum2 + (m-2)*sum(arr))
            else:
                print(maxsum2)

import sys 
def maxSubArraySum(a,n,k): 
       
    max_so_far = -sys.maxsize - 1
    max_ending_here = 0
       
    for i in range(n*k): 
        max_ending_here = max_ending_here + a[i%n] 
        if (max_so_far < max_ending_here): 
            max_so_far = max_ending_here 
  
        if max_ending_here < 0: 
            max_ending_here = 0   
    return max_so_far 



for _ in range(int(input())):
    n,k=map(int,input().split())
    ar=[int(x) for x in input().split()]
    s=sum(ar)
    if s>=0:
        if k==1 or k==2:
            print(maxSubArraySum(ar,n,k))
        else:
            print(maxSubArraySum(ar,n,2)+(k-2)*s)
    else:
        if k==1:
            print(maxSubArraySum(ar,n,k))
        else:
            print(maxSubArraySum(ar,n,2))
        
    

# cook your dish here
tcase=int(input())
for i in range(tcase):
    ninput=input()
    nlist=list(ninput.split(" "))
    A=[]
    B=[]
    numinput=input()
    A=list(numinput.split(" "))
    B=A*int(nlist[1])
    size=int(nlist[0])*int(nlist[1])
    B=[int(i) for i in B]
    max_so_far =B[0] 
    curr_max = B[0] 
    for i in range(1,size): 
        curr_max = max(B[i], curr_max + B[i]) 
        max_so_far = max(max_so_far,curr_max) 
          
    print(max_so_far) 


# cook your dish here
import math
tcases = int(input())
myanswer = []
def programrun(tcases):
    if tcases==0:
        print(0)
        return
    
    def msumfinder(array, n, k):
        msofar = -10000000
        mendnow = 0
        for i in range(n*k):
            mendnow+=array[i%n]
            if mendnow>msofar:
                msofar = mendnow
            if mendnow<0:
                mendnow = 0
        return msofar
        
    for _ in range(0,tcases):
        fline = input().split()
        fline = list(map(int, fline))
        k = fline[1]
        n = fline[0]
        a = [int(x) for x in input().split()]
        sa = sum(a)
        if sa>=0:
            if k==1 or k==2:
                print(msumfinder(a,n,k))
            else:
                print(msumfinder(a,n,2) + (k-2)*sa)
            
        else:
            if k==1:
                print(msumfinder(a,n,1))
            else:
                print(msumfinder(a,n,2))
    
        
        
programrun(tcases)

# cook your dish here
import math
tcases = int(input())
myanswer = []
def programrun(tcases):
    if tcases==0:
        print(0)
        return
    
    def msumfinder(array, n, k):
        msofar = -10000000
        mendnow = 0
        for i in range(n*k):
            mendnow+=array[i%n]
            if mendnow>msofar:
                msofar = mendnow
            if mendnow<0:
                mendnow = 0
        return msofar
        
    for _ in range(0,tcases):
        fline = input().split()
        fline = list(map(int, fline))
        k = fline[1]
        n = fline[0]
        a = [int(x) for x in input().split()]
        sa = sum(a)
        if sa>=0:
            if k==1 or k==2:
                print(msumfinder(a,n,k))
            else:
                print(msumfinder(a,n,2) + (k-2)*sa)
            
        else:
            print(msumfinder(a,n,2))
    
        
        
programrun(tcases)

# cook your dish here
import math
tcases = int(input())
myanswer = []
def programrun(tcases):
    if tcases==0:
        print(0)
        return
    
    def msumfinder(array, n, k):
        msofar = -10000000
        mendnow = 0
        for i in range(n*k):
            mendnow+=array[i%n]
            if mendnow>msofar:
                msofar = mendnow
            if mendnow<0:
                mendnow = 0
        return msofar
        
    for _ in range(0,tcases):
        fline = input().split()
        fline = list(map(int, fline))
        k = fline[1]
        n = fline[0]
        a = [int(x) for x in input().split()]
        sa = sum(a)
        if sa>0:
            if k==1 or k==2:
                print(msumfinder(a,n,k))
            else:
                print(msumfinder(a,n,2) + (k-2)*sa)
            
        else:
            print(msumfinder(a,n,2))
    
        
        
programrun(tcases)

# cook your dish here
import math
tcases = int(input())
myanswer = []
def programrun(tcases):
    if tcases==0:
        print(0)
        return
    
    def msumfinder(array, n, k):
        msofar = -10000000
        mendnow = 0
        for i in range(n*k):
            mendnow+=array[i%n]
            if mendnow>msofar:
                msofar = mendnow
            if mendnow<0:
                mendnow = 0
        return msofar
        
    for _ in range(0,tcases):
        fline = input().split()
        fline = list(map(int, fline))
        k = fline[1]
        n = fline[0]
        a = [int(x) for x in input().split()]
        sa = sum(a)
        if sa>0:
            if k==1 or k==2:
                print(msumfinder(a,n,k))
            else:
                print(msumfinder(a,n,2) + (k-2)*sa)
        elif k==0:
            print(0)
        else:
            print(msumfinder(a,n,2))
    
        
        
programrun(tcases)

# cook your dish here
import math
tcases = int(input())
myanswer = []
def programrun(tcases):
    if tcases==0:
        print(0)
        return
    
    def msumfinder(array, n, k):
        msofar = -10000000
        mendnow = 0
        for i in range(n*k):
            mendnow+=array[i%n]
            if mendnow>msofar:
                msofar = mendnow
            if mendnow<0:
                mendnow = 0
        return msofar
        
    for _ in range(0,tcases):
        fline = input().split()
        fline = list(map(int, fline))
        k = fline[1]
        n = fline[0]
        a = [int(x) for x in input().split()]
        sa = sum(a)
        if sa>0:
            if k==1 or k==2:
                print(msumfinder(a,n,k))
            else:
                print(msumfinder(a,n,2) + (k-2)*sa)
        else:
            print(msumfinder(a,n,2))
    
        
        
programrun(tcases)

# cook your dish here
import math
tcases = int(input())
myanswer = []
def programrun(tcases):
    if tcases==0:
        print(0)
        return
    
    def msumfinder(array, n, k):
        msofar = -10000000
        mendnow = 0
        for i in range(n*k):
            mendnow+=array[i%n]
            if mendnow>msofar:
                msofar = mendnow
            if mendnow<0:
                mendnow = 0
        return msofar
        
    for _ in range(0,tcases):
        fline = input().split()
        fline = list(map(int, fline))
        k = fline[1]
        n = fline[0]
        a = [int(x) for x in input().split()]
        sa = sum(a)
        if sa>0:
            if k==1 or k==2:
                print(msumfinder(a,n,k))
            else:
                print(msumfinder(a,n,2) + (k-2)*sa)
        else:
            print(msumfinder(a,n,k))
    
        
        
programrun(tcases)

# cook your dish here
import math
tcases = int(input())
myanswer = []
def programrun(tcases):
    if tcases==0:
        print(0)
        return
    
    def msumfinder(array, n, k):
        msofar = -10000000
        mendnow = 0
        for i in range(n*k):
            mendnow+=array[i%n]
            if mendnow>msofar:
                msofar = mendnow
            if mendnow<0:
                mendnow = 0
        return msofar
        
    for _ in range(0,tcases):
        fline = input().split()
        fline = list(map(int, fline))
        k = fline[1]
        n = fline[0]
        if n==0:
            print(0)
            continue
        if k==0:
            print(0)
            continue
        
        a = list(map(int, input().split()))
        print(msumfinder(a,n,k))
    
        
        
programrun(tcases)

# cook your dish here
import math
tcases = int(input())
myanswer = []
def programrun(tcases):
    if tcases==0:
        print(0)
        return
    
    def msumfinder(array, n, k):
        msofar = -10000000
        mendnow = 0
        for i in range(n*k):
            mendnow+=array[i%n]
            if mendnow>msofar:
                msofar = mendnow
            if mendnow<0:
                mendnow = 0
        return msofar
        
    for _ in range(0,tcases):
        fline = input().split()
        fline = list(map(int, fline))
        k = fline[1]
        n = fline[0]
        if n==0:
            print(0)
            continue
        if k==0:
            print(0)
            continue
        
        a = list(map(int, input().split()))
        print(msumfinder(a,n,k))
    
        
        
programrun(tcases)

# cook your dish here
import math
tcases = int(input())
myanswer = []
def programrun(tcases):
    if tcases==0:
        print(0)
        return
    
    def msumfinder(array, n, k):
        msofar = -10000000
        mendnow = 0
        for i in range(n*k):
            mendnow+=array[i%n]
            if mendnow>msofar:
                msofar = mendnow
            if mendnow<0:
                mendnow = 0
        return msofar
        
    for _ in range(0,tcases):
        fline = input().split()
        fline = list(map(int, fline))
        k = fline[1]
        n = fline[0]
        if n==0:
            print(0)
            continue
        if k==0:
            print(0)
            continue
        
        a = list(map(int, input().split()))
        
        myanswer.append(msumfinder(a, n, k))
    for element in myanswer:
        print(element)
        
        
programrun(tcases)

def maximum_subarray_sum(a):
    N = len(a)
    max_so_far = -float('inf')
    max_ending_here = 0

    start = 0
    end = 0
    s = 0
    for i in range(N):
        max_ending_here += a[i]
        if(max_ending_here>max_so_far):
            max_so_far = max_ending_here
            start = s
            end = i
        if(max_ending_here<0):
            max_ending_here = 0
            s = i+1
    return start,end

# a = [-1,-2,-3,-4,-5]
# print(maximum_subarray_sum(a))

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


    if(K==1):
        s,e = maximum_subarray_sum(A)
        ans.append(sum(A[s:e+1]))
    else:
        s,e = maximum_subarray_sum(A+A)
        # print('$',s,e,sum(A[2:3]))
        if(e<N):
            ans.append(sum(A[s:e+1]))
        else:
            e -= N
            ans.append( max(sum(A[s:])+sum(A)*(K-2)+sum(A[:e+1]), sum((A+A)[s:e+N+1]) ) )

for i in ans:
    print(i)

def maximum_subarray_sum(a):
    N = len(a)
    max_so_far = -float('inf')
    max_ending_here = 0

    start = 0
    end = 0
    s = 0
    for i in range(N):
        max_ending_here += a[i]
        if(max_ending_here>max_so_far):
            max_so_far = max_ending_here
            start = s
            end = i
        if(max_ending_here<0):
            max_ending_here = 0
            s = i+1
    return start,end

# a = [-1,-2,-3,-4,-5]
# print(maximum_subarray_sum(a))

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


    if(K==1):
        s,e = maximum_subarray_sum(A)
        ans.append(sum(A[s:e+1]))
    else:
        s,e = maximum_subarray_sum(A+A)
        # print('$',s,e,sum(A[2:3]))
        if(e<N):
            ans.append(sum(A[s:e+1]))
        else:
            e -= N
            ans.append( max( sum(A[s:])+sum(A)*(K-2)+sum(A[:e+1]), sum(A[s:e+1]) ) )

for i in ans:
    print(i)

def maximum_subarray_sum(a):
    N = len(a)
    max_so_far = -float('inf')
    max_ending_here = 0

    start = 0
    end = 0
    s = 0
    for i in range(N):
        max_ending_here += a[i]
        if(max_ending_here>max_so_far):
            max_so_far = max_ending_here
            start = s
            end = i
        if(max_ending_here<0):
            max_ending_here = 0
            s = i+1
    return start,end

# a = [-1,-2,-3,-4,-5]
# print(maximum_subarray_sum(a))

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


    if(K==1):
        s,e = maximum_subarray_sum(A)
        ans.append(sum(A[s:e+1]))
    else:
        s,e = maximum_subarray_sum(A+A)
        # print('$',s,e,sum(A[2:3]))
        if(e<N):
            ans.append(sum(A[s:e+1]))
        else:
            e -= N
            ans.append(sum(A[s:])+sum(A)*(K-2)+sum(A[:e+1]))

for i in ans:
    print(i)


# cook your dish here
import sys
t = int(input())
for _ in range(t):
    N,k = map(int,input().split())
    A = list(map(int,input().split()))
    B = A*k
    max_ = -(sys.maxsize)-1
    value = 0
    for i in range(len(B)):
        value = value + B[i]
        if value>max_:
            max_ = value
        if value<0:
            value = 0
    print(max_)

def kadane(l):
	current_sum,best_so_far=0,-9999999999999
	for i in l:
		current_sum+=i
		if best_so_far<current_sum:
			best_so_far=current_sum
		if current_sum<0:
			current_sum=0
	return best_so_far
def max_sum(l,k):
	if k==1:
		ans=kadane(l)
		return ans
	current_prefix_sum,best_prefix_sum=0,-99999999999999
	current_postfix_sum,best_postfix_sum=0,-9999999999999
	total_sum=0
	for i in l:
		current_prefix_sum+=i
		best_prefix_sum=max(current_prefix_sum,best_prefix_sum)
	total_sum=current_prefix_sum
	for i in range(len(l)-1,-1,-1):
		current_postfix_sum+=l[i]
		best_postfix_sum=max(current_postfix_sum,best_postfix_sum)
	if total_sum<0:
		ans=max(best_prefix_sum+best_postfix_sum,kadane(l))
	else:
		ans=max(best_prefix_sum+best_postfix_sum+((k-2)*total_sum),kadane(l))
	return ans
t=int(input())
while t>0:
	n,k=map(int,input().split())
	l=list(map(int,input().split()))
	print(max_sum(l,k))
	t-=1

# cook your dish here
for i in range(int(input())):
    n,k = (map(int,input().split()))
    l = list(map(int,input().split()))
    if k == 1: 
        c_sum = l[0]
        m_sum = l[0]
        for i in range(1,n): 
            c_sum = max(l[i],c_sum + l[i])
            m_sum = max(m_sum,c_sum)
        print(m_sum)
    else: 
        s = sum(l)
        l *= 2
        j = 1
        c_sum = l[0]
        m_sum = l[0]
        while j < 2*n: 
            if l[j] > c_sum + l[j]: 
                c_sum = l[j]
            else: 
                c_sum += l[j]
            if c_sum > m_sum: 
                m_sum = c_sum
            j+=1
        if s <= 0: 
            print(m_sum)
        else:
            print(m_sum + (k - 2)*s)


# cook your dish here
import sys
def maximum_subarray_sum(arr,n,k):
    if k==1: return kadane(arr)
    one_sum=sum(arr)
    a=arr+arr
    if one_sum>0: return kadane(a) + (k-2)*one_sum
    return kadane(a)

def kadane(a):
    best_sum=float('-inf')
    curr_sum=0

    for i in a:
        curr_sum=curr_sum+i
       
        if curr_sum<i: curr_sum=i
        best_sum=max(best_sum,curr_sum)
    return best_sum


def __starting_point():
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    ans=[] #array to store maximum sum of all data sets
    j=1 #starting point of first data set

    t = data[0]
    for i in range(t):
        n=data[j]
        k=data[j+1]
        arr=data[j+2:j+2+n]
        ans.append(maximum_subarray_sum(arr,n,k))
        j=j+2+n
    for x in ans:
        print(x)

__starting_point()

# cook your dish here
import sys
def maximum_subarray_sum(arr,n,k):
    if k==1: return kadane(arr)
    one_sum=sum(arr)
    a=arr+arr
    if one_sum>0: return kadane(a) + (k-2)*one_sum
    return kadane(a)

def kadane(a):
    best_sum=float('-inf')
    curr_sum=0

    for i in a:
        curr_sum=curr_sum+i
        best_sum=max(best_sum,curr_sum)
        if curr_sum<0: curr_sum=0
    return best_sum


def __starting_point():
    input = sys.stdin.read()
    data = list(map(int, input.split()))
    ans=[] #array to store maximum sum of all data sets
    j=1 #starting point of first data set

    t = data[0]
    for i in range(t):
        n=data[j]
        k=data[j+1]
        arr=data[j+2:j+2+n]
        ans.append(maximum_subarray_sum(arr,n,k))
        j=j+2+n
    for x in ans:
        print(x)

__starting_point()