#include <bits/stdc++.h>

#define ll long long
#define vec vector
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x.size())
#define pii pair < int, int >
#define f first
#define s second

using namespace std;

template <typename T>
bool umn (T &a, T b) {return a > b ? (a = b, 1) : 0; }
template <typename T>
bool umx (T &a, T b) {return a < b ? (a = b, 1) : 0; }

const int N = 3e5 + 5;
const int oo = 2e9;
const ll OO = 1e18;
const int mod = 1e9 + 7;

int add (int x, int y) {
    x += y;
    if (x >= mod)
        x -= mod;
    return x >= 0 ? x : x + mod;
}

int mul (int x, int y) {
    return (1ll * x * y) % mod;
}

int bpow (int a, int b) {
    if (b == 0)
        return 1;
    if (b % 2)
        return mul(bpow(a, b - 1), a);
    int t = bpow(a, b / 2);
    return mul(t, t);
}

ll a[N], b[N], n, m;
ll res = -OO;

void r (int l) {
    if (l == m) {
        umx(res, a[0] + a[1]);
        return;
    }
    a[0] = b[l] - a[0];
    r(l + 1);
    a[0] = -a[0] + b[l];
    if (n > 1) {
        a[1] = b[l] - a[1];
        r(l + 1);
        a[1] = -a[1] + b[l];
    }
}

ll dp[N][2];

void slv () {
    cin >> n >> m;
    set < int > st;
    for (int i = 0; i < m; ++i) {
        cin >> b[i];
        st.insert(b[i]);
    }

    if (sz(st) <= 2) {
        int m1 = *st.begin(), m2 = *--st.end(), c = n;
        res = 0;
        for (int i = m - 1; i >= 0; --i) {
            if (b[i] == m2) {
                if (c) {
                    c--;
                    res += b[i];
                } else {
                    c++;
                    res -= b[i];
                }
            } else {
                if (c == n) {
                    res += b[i];
                    --c;
                } else {
                    res -= b[i];
                    c++;
                }
            }
        }
        cout << res << "\n";
        return;


    }

    res = -OO;
    int c = 0;
    for (int i = 0; i <= n; ++i)
        dp[i][0] = dp[i][1] = -OO;
    dp[n][c] = 0;
    for (int i = m - 1; i >= 0; --i) {
        int cc = c ^ 1;
        for (int j = 0; j <= n; ++j) {
            if (j)
                umx(dp[j - 1][cc], dp[j][c] + b[i]);
            if (j != n)
                umx(dp[j + 1][cc], dp[j][c] - b[i]);
        }

        for (int j = 0; j <= n; ++j) {
            dp[j][c] = dp[j][cc];
            dp[j][cc] = -OO;
        }
    }
    for (int j = 0; j <= n; ++j)
        umx(res, dp[j][c]);
    cout << res << "\n";
}

int main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        slv();
    }
}
