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.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Dynamic programming

Greedy algorithms


Solutions:
def max_sum(arr):
	max_till_now = -1000000
	current_sum = 0
	for i in range(len(arr)):
		if current_sum < 0:
			current_sum = 0
		current_sum += arr[i]
		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)
	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:
		case_1_max_sum = max_sum(A)
		case_2_max_sum = Max_Suffix_Sum + Max_Prefix_Sum
		return max([case_1_max_sum, case_2_max_sum])
	else:
		case_1_max_sum = max_sum(A)
		case_2_max_sum = Max_Suffix_Sum + (k - 2) * sum_A + Max_Prefix_Sum
		return max([case_1_max_sum, case_2_max_sum])
T = int(input())
for i in range(T):
	[N, k] = list(map(int, input().split(' ')))
	A = list(map(int, input().split(' ')))
	answer = solve(A, k)
	print(answer)


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	l = [int(x) for x in input().split()]
	aa = sum(l)
	if k == 1:
		a = l[:]
		maxi = -999999999
		sumn = 0
		for i in a:
			sumn += i
			if maxi < sumn:
				maxi = sumn
			if sumn < 0:
				sumn = 0
		print(maxi)
		continue
	if aa > 0:
		a = l[:] * 2
		maxi = -999999999
		sumn = 0
		for i in a:
			sumn += i
			if maxi < sumn:
				maxi = sumn
			if sumn < 0:
				sumn = 0
		print(maxi + (k - 2) * aa)
		continue
	else:
		a = l[:] * 2
		maxi = -999999999
		sumn = 0
		for i in a:
			sumn += i
			if maxi < sumn:
				maxi = sumn
			if sumn < 0:
				sumn = 0
		print(maxi)


import sys

def maxsum(l):
	ans = -sys.maxsize - 1
	cur = 0
	for i in l:
		cur = max(cur + i, i)
		ans = max(ans, cur)
	return ans
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	s = 0
	for i in a:
		s += i
	if k == 1:
		ans = maxsum(a)
		print(ans)
	elif s < 0:
		b = []
		for i in range(2):
			for j in a:
				b.append(j)
		print(maxsum(b))
	else:
		b = []
		for i in range(2):
			for j in a:
				b.append(j)
		t = maxsum(b)
		print(t + (k - 2) * s)


import sys
minn = -sys.maxsize - 1
T = int(input())

def kadane(arr, n):
	(cur_sum, min_sum) = (0, minn)
	for i in range(n):
		cur_sum += arr[i]
		if min_sum < cur_sum:
			min_sum = cur_sum
		if cur_sum < 0:
			cur_sum = 0
	return min_sum
for _ in range(T):
	(n, k) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	cur_sum = sum(arr)
	kad = kadane(arr, n)
	if k == 1:
		print(kad)
	else:
		(cur_pre, cur_suf) = (0, 0)
		(max_pre, max_suf) = (minn, minn)
		for i in range(n):
			cur_suf += arr[i]
			max_suf = max(cur_suf, max_suf)
		suf = max_suf
		for i in range(n - 1, -1, -1):
			cur_pre += arr[i]
			max_pre = max(cur_pre, max_pre)
		pre = max_pre
		if cur_sum < 0:
			print(max(suf + pre, kad))
		elif cur_sum >= 0:
			a1 = pre + suf + cur_sum * (k - 2)
			print(max(a1, kad))


def kadanes(arr):
	cursum = arr[0]
	maxsum = arr[0]
	for i in range(1, len(arr)):
		if cursum >= 0:
			cursum += arr[i]
		else:
			cursum = arr[i]
		maxsum = max(maxsum, cursum)
	return maxsum

def kadanesOftwo(arr):
	narr = arr[:] + arr[:]
	return kadanes(narr)
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr_sum = sum(arr)
	if k == 1:
		print(kadanes(arr))
	elif arr_sum < 0:
		print(kadanesOftwo(arr))
	else:
		print(kadanesOftwo(arr) + (k - 2) * arr_sum)


def kadanes(nums):
	currentSum = float('-inf')
	overallSum = float('-inf')
	for x in range(len(nums)):
		tempSum = currentSum + nums[x]
		if nums[x] < tempSum:
			currentSum = tempSum
		else:
			currentSum = nums[x]
		if currentSum > overallSum:
			overallSum = currentSum
	return overallSum
T = int(input())
while T > 0:
	T -= 1
	(N, K) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	if K == 1:
		print(kadanes(A))
	else:
		arrSum = sum(A)
		A = 2 * A
		if arrSum < 0:
			print(kadanes(A))
		else:
			print(kadanes(A) + (K - 2) * arrSum)


from sys import stdin, stdout
input = stdin.readline

def func(arr):
	n = len(arr)
	(maxsum, total) = (0, 0)
	neg_arr = [arr[i] for i in range(n) if arr[i] < 0]
	neg = len(neg_arr)
	if neg == n:
		return max(arr)
	for i in range(n):
		total += arr[i]
		if total < 0:
			total = 0
		else:
			maxsum = max(maxsum, total)
	return maxsum
t = int(input().strip())
for _ in range(t):
	(n, k) = list(map(int, input().strip().split()))
	arr = list(map(int, input().strip().split()))
	if k == 1:
		print(func(arr))
	elif k == 2:
		a = func(arr)
		b = func(arr + arr)
		print(max(a, b))
	else:
		a = func(arr)
		b = func(arr + arr)
		c = func(arr + arr + arr)
		diff1 = b - a
		diff2 = c - b
		ans = b + (k - 2) * diff2
		print(ans)


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 = []
	j = 1
	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()


def subarr(arr):
	m = float('-inf')
	s = 0
	for i in arr:
		s = s + i
		m = max(m, s)
		if s < 0:
			s = 0
	return m
t = int(input())
out = []
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	z = subarr(arr)
	s = sum(arr)
	arr = arr + arr
	c = subarr(arr)
	if k == 1:
		out.append(z)
	elif s >= 0:
		out.append(c + s * (k - 2))
	else:
		out.append(c)
for i in out:
	print(i)


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)


def max_sum_array(a):
	max_so_far = 0
	max_ending_here = 0
	for i in range(len(a)):
		max_ending_here = max_ending_here + a[i]
		if max_ending_here > max_so_far:
			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) = list(map(int, input().split()))
	array = list(map(int, input().split()))
	max_array = max_sum_array(array)
	max_double_array = max_sum_array(array + array)
	sum_array = sum(array)
	max_starting_0 = 0
	max_ending_here = 0
	for i in range(len(array)):
		max_ending_here = max_ending_here + array[i]
		if max_ending_here > max_starting_0:
			max_starting_0 = max_ending_here
	max_ending_j = 0
	max_ending_here = 0
	j = len(array) - 1
	while j >= 0:
		max_ending_here = max_ending_here + array[j]
		if max_ending_here > max_ending_j:
			max_ending_j = max_ending_here
		j = j - 1
	max_sum = max_array
	if max_sum < max_double_array:
		max_sum = max_double_array
	if max_sum < K * sum_array:
		max_sum = K * sum_array
	if max_sum < max_ending_j + (K - 2) * sum_array + max_starting_0:
		max_sum = max_ending_j + (K - 2) * sum_array + max_starting_0
	flag = 0
	max_element = array[0]
	for i in range(len(array)):
		if array[i] > 0:
			flag = 1
		if max_element < array[i]:
			max_element = array[i]
	if flag == 0:
		max_sum = max_element
		max_array = max_element
	if K > 1:
		print(max_sum)
	else:
		print(max_array)


import sys
inpu = sys.stdin.readline
for _ in range(int(inpu())):
	(n, k) = map(int, inpu().split())
	nums = list(map(int, inpu().split(' ')))
	ms = nums[0]
	cs = nums[0]
	s = nums[0]
	check = nums[0]
	for i in range(1, n):
		s += nums[i]
		check = max(check, s)
		if cs < 0:
			cs = 0
		cs += nums[i]
		ms = max(cs, ms)
	q = nums[::-1]
	ch = q[0]
	ss = q[0]
	for i in range(1, n):
		ss += q[i]
		ch = max(ch, ss)
	if k == 1:
		print(ms)
		continue
	a = nums * 2
	mp = ms
	for i in range(n, len(a)):
		if cs < 0:
			cs = 0
		cs += a[i]
		mp = max(cs, mp)
	ch += s * (k - 2) + check
	print(max(mp, ms, ch))


def kConcatination(B):
	maxSum = -10000000000.0
	tempSum = 0
	for i in range(len(B)):
		tempSum = max(tempSum + B[i], B[i])
		maxSum = max(maxSum, tempSum)
	return maxSum
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = list(map(int, input().split()))
	if k == 1:
		print(kConcatination(A))
	else:
		tSum = sum(A)
		maxSum = kConcatination(2 * A)
		if tSum > 0:
			maxSum += tSum * (k - 2)
		print(maxSum)


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)


def kadane(arr):
	c_m = arr[0]
	o_m = arr[0]
	s = arr[0]
	for i in range(1, len(arr)):
		s += arr[i]
		if arr[i] >= s:
			c_m = arr[i]
			s = arr[i]
			o_m = max(c_m, o_m)
		else:
			c_m = s
			o_m = max(c_m, o_m)
	return o_m
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	sumofarr = sum(arr)
	if k == 1:
		print(kadane(arr))
	elif sumofarr < 0:
		print(kadane(arr * 2))
	else:
		temp = kadane(arr * 2) + (k - 2) * sumofarr
		print(temp)


t = int(input())
for test in range(t):
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	s = sum(l)
	maxSum = l[0]
	curSum = l[0]
	i = 1
	while i < len(l):
		curSum = max(curSum + l[i], l[i])
		if curSum > maxSum:
			maxSum = curSum
		i += 1
	if maxSum == sum(l):
		print(maxSum * k)
	elif k == 1:
		print(maxSum)
	else:
		ms = maxSum
		maxSum = l[0]
		curSum = l[0]
		i = 1
		l *= 2
		while i < len(l):
			curSum = max(curSum + l[i], l[i])
			if curSum > maxSum:
				maxSum = curSum
			i += 1
		if s > 0:
			print((k - 2) * s + maxSum)
		else:
			print(maxSum)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	curMax = maxSum = total = l[0]
	for i in range(1, n * min(k, 2)):
		curMax = max(curMax + l[i % n], l[i % n])
		maxSum = max(maxSum, curMax)
		if i < n:
			total += l[i]
	if total > 0 and k > 2:
		maxSum += total * (k - 2)
	print(maxSum)


def kadne_sum(arr, n):
	currSum = 0
	maxSum = float('-inf')
	for i in range(n):
		currSum += arr[i]
		if maxSum < currSum:
			maxSum = currSum
		if currSum < 0:
			currSum = 0
	return maxSum

def max_subarray_sum(arr, n, k):
	kadne_sum_value = kadne_sum(arr, n)
	if k == 1:
		return kadne_sum_value
	curr_prefix_sum = 0
	curr_suffix_sum = 0
	prefix_sum = float('-inf')
	suffix_sum = float('-inf')
	for i in range(n):
		curr_prefix_sum += arr[i]
		prefix_sum = max(curr_prefix_sum, prefix_sum)
	li_sum = curr_prefix_sum
	for i in range(n - 1, -1, -1):
		curr_suffix_sum += arr[i]
		suffix_sum = max(suffix_sum, curr_suffix_sum)
	ans = 0
	if li_sum < 0:
		ans = max(suffix_sum + prefix_sum, kadne_sum_value)
	else:
		ans = max(suffix_sum + prefix_sum + (k - 2) * li_sum, kadne_sum_value)
	return ans
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	print(max_subarray_sum(li, n, k))


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


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)


def findMaxSubArray(arr, mx):
	MSA = mx
	sm = 0
	for x in arr:
		if sm + x > 0:
			sm += x
			MSA = max(MSA, sm)
		else:
			sm = 0
	return MSA
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	mx = max(arr)
	mx = max(mx, findMaxSubArray(arr, mx))
	if k > 1:
		mx = max(mx, findMaxSubArray(arr + arr, mx))
		if k > 2:
			mx = max(mx, mx + sum(arr) * (k - 2))
	print(mx)


def solve(arr, size):
	maxans = -10 ** 9
	pref = 0
	for i in range(size):
		pref += arr[i]
		maxans = max(maxans, pref)
		if pref < 0:
			pref = 0
	return maxans
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	if k == 1:
		print(solve(arr, n))
	else:
		summ = sum(arr)
		if summ <= 0:
			print(solve(arr + arr, n * 2))
		else:
			print(solve(arr + arr, n * 2) + (k - 2) * summ)


import sys

def kadane(arr):
	if len(arr) == 0:
		return 0
	ans = -sys.maxsize
	cur = 0
	for i in arr:
		cur = max(cur + i, i)
		ans = max(ans, cur)
	return ans
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	s = sum(a)
	if k == 1:
		ans = kadane(a)
		print(ans)
		continue
	b = []
	for i in range(2):
		for j in a:
			b.append(j)
	ans = kadane(b)
	if s < 0:
		print(ans)
	else:
		ans = ans + (k - 2) * s
		print(ans)


def kanade(a, size):
	max_so_far = a[0]
	curr_max = a[0]
	for i in range(1, size):
		curr_max = max(a[i], curr_max + a[i])
		max_so_far = max(max_so_far, curr_max)
	return max_so_far
for t in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	if k == 1:
		print(kanade(arr, len(arr)))
	elif sum(arr) < 0:
		print(kanade(2 * arr, len(2 * arr)))
	else:
		temp = kanade(2 * arr, len(2 * arr)) + (k - 2) * sum(arr)
		print(temp)


def li():
	return list(map(int, input().split()))

def si():
	return input().split()

def ii():
	return int(input())

def ip():
	return input()

def maxum(a, n):
	max_so_far = -1e+19
	curr_max = 0
	for i in range(n):
		curr_max = max(a[i], curr_max + a[i])
		max_so_far = max(max_so_far, curr_max)
	return max_so_far
for tastcas in range(int(input())):
	(n, k) = li()
	a = li()
	if k == 1:
		print(maxum(a, n))
		continue
	s = sum(a)
	ans = maxum(a + a, 2 * n)
	if s >= 0:
		ans += (k - 2) * s
	print(ans)


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)


def maxSumSubarray(B):
	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)):
		B[i] = A[i]
		(ti, j) = (i, 1)
		while j < K:
			B[ti + len(A)] = A[i]
			ti += len(A)
			j += 1
	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


def heler_kadane(arr, n):
	max1 = arr[0]
	max_point = arr[0]
	for i in range(1, n):
		max1 = max(arr[i], max1 + arr[i])
		max_point = max(max1, max_point)
	return max_point
t = int(input())
for i in range(0, t):
	l = list(map(int, input().split()))
	n = l[0]
	k = l[1]
	arr = list(map(int, input().split()))
	arrb = []
	if k == 1:
		maxsum = heler_kadane(arr, n)
	elif k == 2:
		for j in range(0, 2 * n):
			arrb.append(arr[j % n])
		maxsum = heler_kadane(arrb, 2 * n)
	elif k == 3:
		for j in range(0, 3 * n):
			arrb.append(arr[j % n])
		maxsum = heler_kadane(arrb, 3 * n)
	else:
		sum = 0
		for j in range(0, n):
			sum = sum + arr[j]
		for j in range(0, 2 * n):
			arrb.append(arr[j % n])
		for j in range(0, k - 3):
			arrb.append(sum)
		for j in range(0, n):
			arrb.append(arr[j])
		maxsum = heler_kadane(arrb, k - 3 + 3 * n)
	print(maxsum)


def mxarr(arr):
	max1 = arr[0]
	maxpo = arr[0]
	for i in range(1, len(arr)):
		max1 = max(arr[i], arr[i] + max1)
		maxpo = max(max1, maxpo)
		i += 1
	return maxpo
t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	n = l[0]
	k = l[1]
	arr = list(map(int, input().split()))
	if k == 1:
		maxpo = mxarr(arr)
	else:
		sum = 0
		for i in range(len(arr)):
			sum += arr[i]
		newarr = arr
		for i in range(len(arr)):
			newarr.append(arr[i])
		maxpo = max(mxarr(newarr), mxarr(newarr) + sum * (k - 2))
	print(maxpo)


import sys
t = int(input())
while t > 0:
	list1 = list(map(int, input().split()))
	list2 = list(map(int, input().split()))
	n = list1[0]
	k = list1[1]

	def kadane(li):
		max_so_far = 0
		max_ending_here = -sys.maxsize
		for x in li:
			max_so_far += x
			if max_so_far > max_ending_here:
				max_ending_here = max_so_far
			if max_so_far < 0:
				max_so_far = 0
		return max_ending_here
	li = []
	sum = 0
	for x in list2:
		li.append(x)
	for x in list2:
		sum += x
		li.append(x)
	if k == 1:
		ans = kadane(list2)
	elif sum >= 0:
		ans = kadane(li)
		ans += (k - 2) * sum
	elif sum < 0:
		ans = kadane(li)
	print(ans)
	t -= 1


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	a = [int(i) for i in input().split()]
	pre = [0] * n
	suf = [0] * n
	bs = suf[-1] = a[-1]
	bp = pre[0] = a[0]
	for i in range(1, n):
		pre[i] = pre[i - 1] + a[i]
		suf[-(i + 1)] = suf[-i] + a[-(i + 1)]
		if bp < pre[i]:
			bp = pre[i]
		if bs < suf[-(i + 1)]:
			bs = suf[-(i + 1)]
	kad = a[0]
	cs = a[0]
	for i in range(1, n):
		cs += a[i]
		if cs > kad:
			kad = cs
		if cs <= 0:
			cs = 0
	res = 0
	if pre[-1] >= 0 and k >= 2:
		res = (k - 2) * pre[-1] + bp + bs
	elif pre[-1] < 0 and k >= 2:
		res = max(bp + bs, kad)
	else:
		res = kad
	print(res)


def sum_of_arr(l2):
	res = 0
	for i in l2:
		res += i
	return res
t = int(input())
for j in range(0, t):
	l1 = [int(x) for x in input().split()]
	n = l1[0]
	k = l1[1]
	l2 = [int(x) for x in input().split()]
	l3 = []
	for i in l2:
		l3.append(i)
	if k == 1:
		max_sum = 0
		curr_sum = 0
		for i in range(0, n):
			if curr_sum + l2[i] > 0:
				curr_sum += l2[i]
			else:
				curr_sum = 0
			max_sum = max(max_sum, curr_sum)
		max_sum = max(max_sum, curr_sum)
		if max(l2) < 0:
			max_sum = max(l2)
		ans = max_sum
	else:
		l2 += l2
		max_sum = 0
		curr_sum = 0
		for i in range(0, 2 * n):
			if curr_sum + l2[i] > 0:
				curr_sum += l2[i]
			else:
				curr_sum = 0
			max_sum = max(max_sum, curr_sum)
		max_sum = max(max_sum, curr_sum)
		if max(l2) < 0:
			max_sum = max(l2)
		ans = max_sum + max(0, sum_of_arr(l3)) * (k - 2)
	print(ans)


from math import inf

def kadanes_algo(arr):
	max_so_far = -inf
	curr_sum = 0
	for i in arr:
		curr_sum = curr_sum + i
		if max_so_far < curr_sum:
			max_so_far = curr_sum
		if curr_sum < 0:
			curr_sum = 0
	return max_so_far

def maxarraysum(arr, n, k):
	kadanes_sum = kadanes_algo(arr)
	if k == 1:
		return kadanes_sum
	(curr_preffix_sum, curr_suffix_sum) = (0, 0)
	(max_priffix_sum, max_suffix_sum) = (-inf, -inf)
	for i in range(n):
		curr_preffix_sum = curr_preffix_sum + arr[i]
		max_priffix_sum = max(max_priffix_sum, curr_preffix_sum)
	total_sum = curr_preffix_sum
	for i in range(n - 1, -1, -1):
		curr_suffix_sum = curr_suffix_sum + arr[i]
		max_suffix_sum = max(max_suffix_sum, curr_suffix_sum)
	if total_sum < 0:
		return max(max_priffix_sum + max_suffix_sum, kadanes_sum)
	else:
		return max(max_priffix_sum + max_suffix_sum + total_sum * (k - 2), kadanes_sum)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(maxarraysum(arr, n, k))


def kadanes(seq):
	(max_global, max_current) = (seq[0], seq[0])
	for i in range(1, len(seq)):
		max_current = max(seq[i] + max_current, seq[i])
		if max_current > max_global:
			max_global = max_current
	return max_global
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	arr = list(map(int, input().split()))
	if K == 1:
		m = kadanes(arr)
		print(m)
		continue
	else:
		m = kadanes(arr + arr)
		sum_arr = sum(arr)
		if sum_arr < 0:
			print(m)
		else:
			print(m + sum_arr * (K - 2))


mod = 1000000007
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	om = a[0]
	cm = a[0]
	if k == 1:
		for i in range(1, n, 1):
			cm = max(a[i % n], cm + a[i % n])
			om = max(om, cm)
		print(om)
	else:
		c = 0
		for i in range(n):
			c = c + a[i]
		if c <= 0:
			a = a * 2
			for i in range(1, n * 2, 1):
				cm = max(a[i % n], cm + a[i % n])
				om = max(om, cm)
			print(om)
		else:
			a = a * 2
			for i in range(1, n * 2, 1):
				cm = max(a[i % n], cm + a[i % n])
				om = max(om, cm)
			print(om + (k - 2) * c)


for _ in range(int(input())):
	nk = input()
	nk = list(map(int, nk.split()))
	n = nk[0]
	k = nk[1]
	arr = input()
	arr = list(map(int, arr.split()))
	S = sum(arr)
	maxSum = -2 ** 31
	tempsum = 0
	for i in range(len(arr)):
		tempsum += arr[i]
		tempsum = max(tempsum, arr[i])
		maxSum = max(tempsum, maxSum)
	baseSum = maxSum
	if maxSum == S:
		print(k * S)
	elif k == 1:
		print(maxSum)
	else:
		karr = 2 * arr
		maxSum = -2 ** 31
		tempsum = 0
		for i in range(len(karr)):
			tempsum += karr[i]
			tempsum = max(tempsum, karr[i])
			maxSum = max(tempsum, maxSum)
		if S > 0:
			print((k - 2) * S + maxSum)
		else:
			print(maxSum)


def kadane_solution(A):
	curr_sum = 0
	max_sum = float('-inf')
	for i in range(len(A)):
		if curr_sum < 0:
			curr_sum = 0
		curr_sum += A[i]
		max_sum = max(curr_sum, max_sum)
	return max_sum
t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))[:n]
	res = 0
	if k < 2:
		print(kadane_solution(a), end='\n')
	else:
		k_res = kadane_solution(a + a)
		s = sum(a)
		if s >= 0:
			res = k_res + (k - 2) * s
		else:
			res = k_res
		print(res, end='\n')
	t -= 1


def mgc(arr, n, k):
	s = sum(arr)
	b = []
	if k == 1:
		b.extend(arr)
	else:
		b.extend(arr)
		if s * (k - 2) > 0:
			b.append(s * (k - 2))
		b.extend(arr)
	s = b[0]
	gs = b[0]
	for i in b[1:]:
		s = max(i, s + i)
		gs = max(s, gs)
	return gs
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	print(mgc(arr, n, k))


def kadane(arr: list) -> int:
	current_sum = 0
	max_sum = arr[0]
	for num in arr:
		current_sum += num
		max_sum = max(max_sum, current_sum)
		if current_sum < 0:
			current_sum = 0
	return max_sum

def max_subarr_sum(arr: list, n: int, k: int) -> int:
	kadane_sum = kadane(arr)
	if k == 1:
		return kadane_sum
	current_prefix_sum = 0
	current_suffix_sum = 0
	max_prefix_sum = arr[0]
	for num in arr:
		current_prefix_sum += num
		max_prefix_sum = max(max_prefix_sum, current_prefix_sum)
	max_suffix_sum = arr[-1]
	total_sum = current_prefix_sum
	for num in arr[::-1]:
		current_suffix_sum += num
		max_suffix_sum = max(max_suffix_sum, current_suffix_sum)
	if total_sum < 0:
		return max(max_suffix_sum + max_prefix_sum, kadane_sum)
	else:
		return max(max_suffix_sum + max_prefix_sum + total_sum * (k - 2), kadane_sum)
t = int(input())
for x in range(t):
	n_k = list(map(int, input().split()))
	n = n_k[0]
	k = n_k[1]
	arr = list(map(int, input().split()))
	print(max_subarr_sum(arr, n, k))


for i in range(int(input())):
	(n, k) = map(int, input().split())
	l1 = list(map(int, input().split()))
	g_max = l1[0]
	c_max = l1[0]
	total = sum(l1)
	if k == 1:
		for i in range(1, len(l1)):
			c_max = max(l1[i], c_max + l1[i])
			if c_max > g_max:
				g_max = c_max
		print(g_max)
	elif k > 1 and sum(l1) <= 0:
		l1 = l1 * 2
		for i in range(1, len(l1)):
			c_max = max(l1[i], c_max + l1[i])
			if c_max > g_max:
				g_max = c_max
		print(g_max)
	elif sum(l1) > 0:
		l1 = l1 * 2
		for i in range(1, len(l1)):
			c_max = max(l1[i], c_max + l1[i])
			if c_max > g_max:
				g_max = c_max
		print(g_max + (k - 2) * total)


import sys, math
sys.setrecursionlimit(10 ** 5)

def pro(arr, k):
	n = len(arr)
	s = sum(arr)
	ans = kadane(arr)
	if k == 1:
		print(ans)
		return
	t1 = -math.inf
	c = 0
	for i in range(n):
		c += arr[i]
		t1 = max(t1, c)
	t2 = -math.inf
	c = 0
	for i in range(n - 1, -1, -1):
		c += arr[i]
		t2 = max(t2, c)
	ans = max(ans, t1 + t2, t1 + t2 + (k - 2) * s)
	print(ans)

def kadane(arr):
	n = len(arr)
	maxi = -math.inf
	curr = 0
	for i in range(n):
		curr = max(curr + arr[i], arr[i])
		maxi = max(maxi, curr)
	return maxi
n = int(input())
for i in range(n):
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	pro(arr, k)


def solve(arr, k):

	def kadanes(arr):
		(curr, msf) = (arr[0], arr[0])
		for i in range(1, len(arr)):
			curr = max(curr + arr[i], arr[i])
			msf = max(msf, curr)
		return msf
	S = sum(arr)
	if k == 1:
		return kadanes(arr)
	sumConcat = kadanes(2 * arr)
	if S > 0:
		return sumConcat + (k - 2) * S
	else:
		return sumConcat
tc = int(input())
while tc:
	(n, k) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	print(solve(arr, k))
	tc -= 1


def kadanes_algo(arr):
	dparr = [0] * len(arr)
	ans = dparr[0] = arr[0]
	for i in range(1, len(arr)):
		dparr[i] = max(arr[i], arr[i] + dparr[i - 1])
		ans = max(ans, dparr[i])
	return ans

def solve(arr, k):
	if k == 1:
		print(kadanes_algo(arr))
	else:
		summ = sum(arr)
		newarr = arr * 2
		print(max(kadanes_algo(newarr), kadanes_algo(newarr) + summ * (k - 2)))

def main():
	t = int(input())
	for i in range(t):
		(n, k) = map(int, input().split(' '))
		arr = list(map(int, input().split(' ')))
		solve(arr, k)
main()


import sys

def kadane(a):
	cur = 0
	ans = -sys.maxsize
	for i in a:
		cur = max(cur + i, i)
		ans = max(cur, ans)
	return ans
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(x) for x in input().split()]
	if k == 1:
		t = kadane(a)
		print(t)
		continue
	s = 0
	for i in a:
		s += i
	b = []
	for i in range(2):
		for i in a:
			b.append(i)
	t = kadane(b)
	if s >= 0:
		t += (k - 2) * s
	print(t)


def getMax(arr):
	max_elem = arr[0]
	for elem in arr:
		if elem > max_elem:
			max_elem = elem
	return max_elem

def getBestPrefixSum(arr, n):
	prefix_sum = [elem for elem in arr]
	for i in range(1, n):
		prefix_sum[i] += prefix_sum[i - 1]
	return getMax(prefix_sum)

def getBestSuffixSum(arr, n):
	suffix_sum = [elem for elem in arr]
	for i in range(n - 2, -1, -1):
		suffix_sum[i] += suffix_sum[i + 1]
	return getMax(suffix_sum)

def getKadaneMaxSum(arr, n):
	current_sum = 0
	best_sum = arr[0]
	for i in range(n):
		current_sum += arr[i]
		if best_sum < current_sum:
			best_sum = current_sum
		if current_sum < 0:
			current_sum = 0
	return best_sum

def getEntireArrSum(arr):
	sum = 0
	for elem in arr:
		sum += elem
	return sum

def solve(arr, n, k):
	answer = 0
	if k == 1:
		answer = getKadaneMaxSum(arr, n)
	elif k == 2:
		answer = max(getKadaneMaxSum(arr, n), getBestPrefixSum(arr, n) + getBestSuffixSum(arr, n))
	else:
		array_sum = getEntireArrSum(arr)
		if array_sum > 0:
			answer = max(getKadaneMaxSum(arr, n), getBestPrefixSum(arr, n) + (k - 2) * array_sum + getBestSuffixSum(arr, n))
		else:
			answer = max(getKadaneMaxSum(arr, n), getBestPrefixSum(arr, n) + getBestSuffixSum(arr, n))
	return answer

def main():
	t = int(input())
	while t:
		(n, k) = (int(x) for x in input().split())
		arr = [int(elem) for elem in input().split()]
		print(solve(arr, n, k))
		t -= 1
	return
main()


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


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)


def maxSubarraySum(arr):
	(maxSum, currSum) = (float('-inf'), 0)
	for i in arr:
		if currSum < 0:
			currSum = i
		else:
			currSum += i
		maxSum = max(maxSum, currSum)
	return maxSum
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	arr = l[:]
	for i in range(1, 2):
		arr.extend(l)
	s1 = maxSubarraySum(arr)
	s2 = sum(l)
	if k == 1:
		print(maxSubarraySum(l))
	elif s2 < 0:
		print(s1)
	else:
		print(s1 + (k - 2) * s2)


def kadane(k):
	max_so_far = k[0]
	curr_so_far = k[0]
	for j in range(1, len(k)):
		curr_so_far = max(k[j], curr_so_far + k[j])
		max_so_far = max(max_so_far, curr_so_far)
	return max_so_far
x = int(input())
for i in range(x):
	(y, z) = map(int, input().split())
	ar = list(map(int, input().split()))
	if z == 1:
		print(kadane(ar))
	elif sum(ar) < 0:
		print(kadane(ar * 2))
	else:
		temp = kadane(ar * 2) + (z - 2) * sum(ar)
		print(temp)


def KADANE_s(a):
	curr_sum = 0
	best_sum = float('-inf')
	for i in a:
		curr_sum += i
		if best_sum < curr_sum:
			best_sum = curr_sum
		if curr_sum < 0:
			curr_sum = 0
	return best_sum

def maxSubarrSum(a, n, k):
	k_sum = KADANE_s(a)
	if k == 1:
		return k_sum
	(suffix_sum, max_suffix_sum) = (0, float('-inf'))
	(prefix_sum, max_prefix_sum) = (0, float('-inf'))
	for i in range(n - 1, -1, -1):
		suffix_sum += a[i]
		if max_suffix_sum < suffix_sum:
			max_suffix_sum = suffix_sum
	for i in a:
		prefix_sum += i
		if max_prefix_sum < prefix_sum:
			max_prefix_sum = prefix_sum
	total_sum = prefix_sum
	if total_sum < 0:
		ans = max(max_prefix_sum + max_suffix_sum, k_sum)
	else:
		ans = max(max_prefix_sum + max_suffix_sum + total_sum * (k - 2), k_sum)
	return ans
t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = maxSubarrSum(a, n, k)
	print(ans)


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


import sys
t = int(input())
while t > 0:
	t = t - 1
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	if k == 1:
		globmax = sys.maxsize * -1
		curmax = 0
		for i in range(0, len(a)):
			curmax = curmax + a[i]
			if curmax > globmax:
				globmax = curmax
			if curmax < 0:
				curmax = 0
		print(globmax)
	else:
		summ = sum(a)
		if summ < 0:
			b = []
			for i in range(0, 2):
				for j in range(0, len(a)):
					b.append(a[j])
			globmax = sys.maxsize * -1
			curmax = 0
			for i in range(0, len(b)):
				curmax = curmax + b[i]
				if curmax > globmax:
					globmax = curmax
				if curmax < 0:
					curmax = 0
			print(globmax)
		else:
			b = []
			for i in range(0, 2):
				for j in range(0, len(a)):
					b.append(a[j])
			globmax = sys.maxsize * -1
			curmax = 0
			for i in range(0, len(b)):
				curmax = curmax + b[i]
				if curmax > globmax:
					globmax = curmax
				if curmax < 0:
					curmax = 0
			ans = globmax + (k - 2) * summ
			print(ans)


def maxSubArraySum(array):
	currentSum = array[0]
	answer = array[0]
	for x in array[1:]:
		currentSum = max(currentSum + x, x)
		answer = max(answer, currentSum)
	return answer
t = int(input())
while t != 0:
	t -= 1
	(n, k) = list(map(int, input().split(' ')))
	array = list(map(int, input().split(' ')))
	s = sum(array)
	if k == 1:
		print(maxSubArraySum(array))
	else:
		temp = array + array
		if s >= 0:
			print(s * (k - 2) + maxSubArraySum(temp))
		else:
			print(maxSubArraySum(temp))


for i in range(int(input())):
	import sys
	x = input().split(' ')
	n = int(x[0])
	k = int(x[1])
	data = [int(num) for num in input().split(' ')]
	datas = data * 2 if k > 1 else data
	cs = 0
	ms = -sys.maxsize
	for num in datas:
		cs += num
		ms = max(ms, cs)
		if cs < 0:
			cs = 0
	print(ms + (k - 2) * sum(data) if sum(data) > 0 and k > 1 else ms)


def kadanes(arr):
	c_m = arr[0]
	o_m = arr[0]
	s = arr[0]
	for i in range(1, len(arr)):
		s += arr[i]
		if arr[i] >= s:
			c_m = arr[i]
			s = arr[i]
		else:
			c_m = s
		o_m = max(c_m, o_m)
	return o_m
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	arr = [int(i) for i in input().split()]
	if k == 1:
		print(kadanes(arr))
		continue
	s = sum(arr)
	if s < 0:
		print(kadanes(arr + arr))
		continue
	else:
		print(kadanes(arr + arr) + (k - 2) * s)
		continue


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)
	elif k == 1:
		print(maxSubArraySum(ar, n, k))
	else:
		print(maxSubArraySum(ar, n, 2))


def KCon(arr):
	(flag, temp) = (arr[0], arr[0])
	for i in range(1, len(arr)):
		if flag >= 0:
			flag += arr[i]
		else:
			flag = arr[i]
		temp = max(flag, temp)
	return temp
T = int(input())
res = []
for _ in range(T):
	(N, K) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	if K == 1:
		res.append(KCon(A))
	elif sum(A) < 0:
		res.append(KCon(A * 2))
	else:
		res.append(KCon(A * 2) + (K - 2) * sum(A))
for i in res:
	print(i)


import sys

def kadane(arr, n):
	(curr_sum, max_sum) = (0, max(arr))
	for i in range(n):
		if curr_sum + arr[i] >= 0:
			curr_sum += arr[i]
			max_sum = max(max_sum, curr_sum)
		else:
			curr_sum = 0
	return max_sum
for __ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = kadane(a + a, 2 * n) if k > 1 else kadane(a, n)
	if k > 2:
		ans = max(ans, ans + (k - 2) * sum(a))
	print(ans)


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


t = int(input())

def sum1(a):
	max1 = a[0]
	maxpo = a[0]
	for i in range(1, len(a)):
		max1 = max(a[i], a[i] + max1)
		maxpo = max(max1, maxpo)
		i += 1
	return maxpo
for i in range(t):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	if K == 1:
		max_sum = sum1(A)
	else:
		s = 0
		for i in range(len(A)):
			s += A[i]
		A1 = A
		for i in range(len(A)):
			A1.append(A[i])
		max_sum = max(sum1(A1), sum1(A1) + s * (K - 2))
	print(max_sum)


def kadanes_algo(arr):
	max_sum = 0
	curr_sum = 0
	n = len(arr)
	if max(arr) < 0:
		max_sum = max(arr)
		return max_sum
	i = 0
	while i < n:
		if curr_sum + arr[i] > 0:
			curr_sum += arr[i]
		else:
			curr_sum = 0
		i += 1
		max_sum = max(max_sum, curr_sum)
	return max_sum
t = int(input())
for j in range(0, t):
	l1 = [int(x) for x in input().split()]
	n = l1[0]
	k = l1[1]
	a = [int(x) for x in input().split()]
	val1 = kadanes_algo(a)
	if k == 1:
		print(val1)
	else:
		sum_a = 0
		for i in a:
			sum_a += i
		max_right = a[n - 1]
		val = a[n - 1]
		for i in range(n - 2, -1, -1):
			val += a[i]
			max_right = max(val, max_right)
		max_left = a[0]
		val = a[0]
		for i in range(1, n):
			val += a[i]
			max_left = max(val, max_left)
		val2 = max_right + sum_a * (k - 2) + max_left
		val3 = max_left + max_right
		ans = max(val1, val2, val3)
		print(ans)


def Kadanes(A, n):
	current_sum = 0
	best_sum = -2 ** 31
	for i in range(n):
		current_sum = current_sum + A[i]
		if best_sum < current_sum:
			best_sum = current_sum
		if current_sum < 0:
			current_sum = 0
	return best_sum

def K_concatenation(A, n, k):
	Sum = Kadanes(A, n)
	if k == 1:
		return Sum
	curr_prefix_sum = 0
	curr_suffix_sum = 0
	max_prefix_sum = -2 ** 31
	max_suffix_sum = -2 ** 31
	for i in range(n):
		curr_prefix_sum = curr_prefix_sum + A[i]
		max_prefix_sum = max(max_prefix_sum, curr_prefix_sum)
	totalSum = curr_prefix_sum
	for i in range(n - 1, -1, -1):
		curr_suffix_sum = curr_suffix_sum + A[i]
		max_suffix_sum = max(max_suffix_sum, curr_suffix_sum)
	if totalSum < 0:
		ans = max(max_suffix_sum + max_prefix_sum, Sum)
	else:
		ans = max(max_suffix_sum + max_prefix_sum + totalSum * (k - 2), Sum)
	return ans

def TakeInput():
	arr1 = [int(x) for x in input().split()]
	n = arr1[0]
	k = arr1[1]
	A = [int(y) for y in input().split()]
	return (n, k, A)
t = int(input())
for i in range(t):
	(n, k, A) = TakeInput()
	ans = K_concatenation(A, n, k)
	print(ans)


def kcon(n, k, arr):
	if k < 3:
		return maxSubArray(arr * k)
	sum_arr = sum(arr)
	max_sum_2_kcon = maxSubArray(arr * 2)
	if sum_arr < 0:
		return max_sum_2_kcon
	return max_sum_2_kcon + sum_arr * (k - 2)

def maxSubArray(nums):
	if not nums:
		return 0
	curr_sum = max_sum = nums[0]
	for i in range(1, len(nums)):
		curr_sum = max(nums[i], curr_sum + nums[i])
		max_sum = max(max_sum, curr_sum)
	return max_sum
t = int(input())
for i in range(t):
	(N, K) = map(int, input().split())
	Arr = list(map(int, input().split()))
	res = kcon(N, K, Arr)
	print(res)


import sys
tt = int(input())
for _ in range(0, tt):
	l = list(map(int, input().split()))
	k = l[1]
	darr = list(map(int, input().split()))
	n = len(darr)
	maxsofar = -999999
	maxuphere = 0
	for i in range(0, n * min(k, 2)):
		maxuphere += darr[i % n]
		if maxsofar < maxuphere:
			maxsofar = maxuphere
		if maxuphere < 0:
			maxuphere = 0
	if sum(darr) > 0:
		if k == 1:
			print(maxsofar)
		else:
			print(maxsofar + sum(darr) * (k - 2))
	else:
		print(maxsofar)


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


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [i for i in a] * k
	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(max(new))


def Kandans(arr):
	m = arr[0]
	m1 = arr[0]
	for x in arr[1:]:
		m = max(x, m + x)
		m1 = max(m, m1)
	return m1
for x in range(int(input())):
	(N, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	s = sum(arr)
	if k == 1:
		print(Kandans(arr))
	elif s <= 0:
		print(Kandans(arr + arr))
	else:
		print(Kandans(arr + arr) + (k - 2) * s)


for t in range(0, int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))[:n]
	t = 0
	total = 0
	dp = []
	if k == 1:
		new_arr = arr
	else:
		new_arr = arr * 2
	for i in range(0, len(new_arr)):
		if total < 0:
			total = 0
		total += new_arr[i]
		dp.append(total)
		t = 1
	if k == 1:
		print(max(dp))
	elif sum(arr) > 0:
		print(max(dp) + sum(arr) * (k - 2))
	else:
		print(max(dp))


import sys

def kadane(arr):
	max_so_far = arr[0]
	curr_sum = arr[0]
	for i in range(1, len(arr)):
		curr_sum = max(arr[i], curr_sum + arr[i])
		max_so_far = max(curr_sum, max_so_far)
	return max_so_far

def max_sum(arr, kadane_sum, k):
	if k <= 0:
		return 0
	if k == 1:
		return kadane_sum
	curr_pre_sum = 0
	curr_suf_sum = 0
	max_pre_sum = sys.maxsize * -1
	max_suf_sum = sys.maxsize * -1
	total_sum = 0
	for i in range(len(arr)):
		curr_pre_sum += arr[i]
		max_pre_sum = max(curr_pre_sum, max_pre_sum)
	total_sum = curr_pre_sum
	for i in range(len(arr) - 1, -1, -1):
		curr_suf_sum += arr[i]
		max_suf_sum = max(curr_suf_sum, max_suf_sum)
	if total_sum < 0:
		return max(max_pre_sum + max_suf_sum, kadane_sum)
	else:
		return max(max_pre_sum + max_suf_sum + total_sum * (k - 2), kadane_sum)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	kadane_sum = kadane(arr)
	ans = max_sum(arr, kadane_sum, k)
	print(ans)


def solve(a, n, m):
	max_so_far = a[0]
	curr_max = a[0]
	for i in range(1, m):
		curr_max = max(a[i % n], curr_max + a[i % n])
		max_so_far = max(max_so_far, curr_max)
	return max_so_far
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = [int(x) for x in input().split()]
	if k == 1:
		print(solve(l, n, n))
	else:
		subSum = solve(l, n, 2 * n)
		s = 0
		for i in l:
			s += i
		print(max(subSum, subSum + s * (k - 2)))