#pragma GCC optimize("Ofast,-O3")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
//using ll = int;
using ld = long double;
using ull = unsigned long long;
#define pb push_back
#define all(vec) vec.begin(), vec.end()
#define eb emplace_back
#ifdef LOCAL
#define deb(x) cout << #x << " = " << x << '\n'
#else
#define deb(x) 52
#endif
const ll inf = 1e9 + 11;
const long long INF = (long long)2e18 + 11;
const ll P = 73;
const ll MOD = 1e9 + 7;


bool lmax(ll &x, ll y) {
    if (y > x) {
        x = y;
        return true;
    } else {
        return false;
    }
}


mt19937 gen(52);


struct Node {
    ll x, y, sz, lazy;
    Node *l, *r;

    Node(ll x = 0) : x(x) {
        y = gen();
        sz = 1;
        lazy = 0;
        l = nullptr, r = nullptr;
    }
};

typedef pair<Node*, Node*> Pair;

ll vsize(Node *v) {
    return (v ? v->sz : 0);
}

void upd(Node *v) {
    v->sz = vsize(v->r) + vsize(v->l) + 1;
}

void push(Node *v) {
    if (v) {
        v->x += v->lazy;
        if (v->l) {
            v->l->lazy += v->lazy;
        }
        if (v->r) {
            v->r->lazy += v->lazy;
        }
        v->lazy = 0;
    }
}

struct Treap {
    Node *root = nullptr;

    Node* merge(Node *l, Node *r) {
        push(l), push(r);
        if (!l) {
            return r;
        }
        if (!r) {
            return l;
        }
        if (l->y > r->y) {
            l->r = merge(l->r, r);
            upd(l);
            return l;
        } else {
            r->l = merge(l, r->l);
            upd(r);
            return r;
        }
    }

    Pair split(Node *v, ll k) {
        if (!v) {
            return {nullptr, nullptr};
        }
        push(v);
        if (vsize(v->l) + 1 <= k) {
            Pair q = split(v->r, k - vsize(v->l) - 1);
            v->r = q.first;
            upd(v);
            return {v, q.second};
        } else {
            Pair q = split(v->l, k);
            v->l = q.second;
            upd(v);
            return {q.first, v};
        }
    }

    ll get(Node *v, ll k) {
        push(v);
        if (k == vsize(v->l) + 1) {
            return v->x;
        } else if (k < vsize(v->l) + 1) {
            return get(v->l, k);
        } else {
            return get(v->r, k - vsize(v->l) - 1);
        }
    }

    ll get(ll k) {
        return get(root, k + 1);
    }

    void insert(ll x) {
        root = merge(root, new Node(x));
    }

    void insert(ll k, ll x) {  // after first k
        Pair q = split(root, k);
        root = merge(merge(q.first, new Node(x)), q.second);
    }

    void erase_first() {
        root = split(root, 1).second;
    }

    void erase_last() {
        root = split(root, vsize(root) - 1).first;
    }

    void doit(ll pos, ll x) {
        ll val1 = get(pos), val2 = get(pos + 1);
        insert(pos + 2, val1);
        insert(pos + 3, val2);
        erase_first();
        erase_last();
        Pair q = split(root, pos + 1);
        q.first->lazy -= x;
        q.second->lazy += x;
        root = merge(q.first, q.second);
    }
};


void solve() {
    ll n, m;
    cin >> n >> m;
    vector<ll> x(m);
    for (ll i = 0; i < m; ++i) {
        cin >> x[i];
    }
    reverse(all(x));
    //vector<vector<ll>> dp(m + 1, vector<ll>(n + 1, -INF));
    //dp[0][0] = 0;
    Treap treap;
    treap.insert(0);
    for (ll i = 1; i <= n; ++i) {
        treap.insert(-INF);
    }
    for (ll i = 1; i <= m; ++i) {
        /*for (ll j = 0; j <= n; ++j) {
            if (j > 0) {
                lmax(dp[i][j], dp[i - 1][j - 1] + x[i - 1]);
            }
            if (j < n) {
                lmax(dp[i][j], dp[i - 1][j + 1] - x[i - 1]);
            }
        }*/
        ll pos = 0;
        /*for (ll j = 1; j < n; ++j) {
            if (dp[i - 1][j + 1] - x[i - 1] > dp[i - 1][j - 1] + x[i - 1]) {
                pos = j;
            } else {
                break;
            }
        }*/
        ll l = 0, r = n;
        while (r - l > 1) {
            ll mid = (r + l) >> 1;
            ll v1 = treap.get(mid + 1) - x[i - 1], v2 = treap.get(mid - 1) + x[i - 1];
            if (v1 > v2) {
                l = mid;
            } else {
                r = mid;
            }
        }
        pos = l;
        if (i == 1) {
            pos = 0;
        }
        treap.doit(pos, x[i - 1]);
        /*for (ll j = 0; j <= pos; ++j) {
            lmax(dp[i][j], dp[i - 1][j + 1] - x[i - 1]);
        }
        for (ll j = pos + 1; j <= n; ++j) {
            lmax(dp[i][j], dp[i - 1][j - 1] + x[i - 1]);
        }*/
    }
    ll ans = -INF;
    for (ll i = 0; i <= n; ++i) {
        ans = max(ans, treap.get(i));
    }
    cout << ans;
}


int main() {
#ifdef LOCAL
    freopen("C:/work/untitled/input.txt", "r", stdin);
    freopen("C:/work/untitled/output.txt", "w", stdout);
#endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll cfmode = 1;
    ll tc = 1;
    if (cfmode) {
        cin >> tc;
    }
    while (tc--) {
        solve();
        if (tc) {
            cout << '\n';
        }
    }
}