from functools import lru_cache


# lru_cache(None) mémoise la fonction

for _ in range(int(input())):
    k, n = int(input()), int(input())
    *a, = map(int, input().split())

    @lru_cache(None)
    def ans(k, n):
        """
        profit maximum en utilisant au plus
        k transations et avec la dernière
        vente en n-1
        """
        if n < 2:
            return 0
        if k < 1:
            return 0
        r = ans(k - 1, n)
        e = a[n - 1]
        # ms: profit maximum jusqu'à l'indice
        # s non inclus
        ms = 0
        for s in range(n - 1):
            ms = max(ms, ans(k - 1, s))
            r = max(ms + e - a[s], r)
        return r
    print(max(ans(k, i) for i in range(n+1)))