import random
random.seed(42)
def solve():
    n, m = map(int, input().split())
    xs = list(map(int, input().split()))
    best = 0
    for _ in range(m ** 6):
        go = [random.randint(0,n-1) for _ in range(m)]
        a = [0 for _ in range(n)]
        for i,goi in enumerate(go):
            a[goi] = xs[i] - a[goi]
        best = max(best, sum(a))
    print(best)

for _ in range(int(input())):
    solve()