import sys
input = lambda: sys.stdin.readline().rstrip("\r\n")

for t in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    dp = [-float("inf")]*(2*n + 2)
    dp[0] = 0
    for _ in range(k):
        dp2 = [-float("inf")]*(2*n + 2)
        for i in range(_, n):
            #ends at index, doesnt end at index
            p, q = 2*i + 2, 2*i + 3
            dp2[p] = max(dp[p-2] + a[i], dp2[p-2] + a[i], dp2[p-1] + a[i])
            dp2[q] = max(dp2[p], dp2[p-2], dp[p-1] + a[i], dp[p-2] + a[i], dp2[p-1])
        dp = list(dp2)
    print(dp[-1])