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.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'def max_sum(arr):\n    # Finds the maximum sum of sub-arrays of arr\n    max_till_now = -1000000 #minimum possible number \n    current_sum = 0\n    for i in range(len(arr)):\n        if current_sum < 0:\n            # If sum of previous elements is negative, then ignore them. Start fresh\n            # with `current_sum = 0`\n            current_sum = 0\n        \n        current_sum += arr[i]\n        \n        # Update max\n        if max_till_now < current_sum:\n            max_till_now = current_sum\n    \n    return max_till_now\n\n\ndef solve(A, k):\n    if k == 1:\n        return max_sum(A)\n    # Find sum of elements of A\n    sum_A = 0\n    for i in range(len(A)):\n        sum_A += A[i]\n    \n    Max_Suffix_Sum = -1000000\n    current = 0\n    for i in range(len(A)):\n        current += A[-i-1]\n        if current > Max_Suffix_Sum:\n            Max_Suffix_Sum = current\n\n    Max_Prefix_Sum = -1000000\n    current = 0\n    for i in range(len(A)):\n        current += A[i]\n        if current > Max_Prefix_Sum:\n            Max_Prefix_Sum = current\n\n    if sum_A <= 0:\n        # Check two cases:\n\n        # Case 1 : Check the max_sum of A\n        case_1_max_sum = max_sum(A)\n        \n        # Case 2 : Check the max_sum of A + A\n        case_2_max_sum = Max_Suffix_Sum + Max_Prefix_Sum\n\n        # Return the maximum of the two cases\n        return max([case_1_max_sum, case_2_max_sum])\n\n    else: # if sum_A > 0\n        #Check two cases:\n\n        # Case 1 : Check the max_sum of A\n        case_1_max_sum = max_sum(A)\n\n        # Case 2\n        # Max sum = Max_Suffix_Sum + (k - 2)*sum_A + Max_Prefix_Sum       \n        \n        case_2_max_sum = Max_Suffix_Sum + (k - 2)*sum_A + Max_Prefix_Sum\n        \n        # Return the maximum of the two cases\n        return max([case_1_max_sum, case_2_max_sum])\n\n\n# Main\nT = int(input()) # No of test cases\nfor i in range(T):\n    [N, k] = list(map(int, input().split(" ")))\n    A = list(map(int, input().split(" ")))\n    \n    answer = solve(A,k)\n    print(answer)'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 13373