#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
#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;
    ll l, r;

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


const ll N = 4e5;
Node nodes[N];
ll CUR = 1;

typedef pair<ll, ll> Pair;

ll vsize(ll v) {
    return (v ? nodes[v].sz : 0);
}

void upd(ll v) {
    nodes[v].sz = vsize(nodes[v].r) + vsize(nodes[v].l) + 1;
}

void push(ll v) {
    if (v) {
        nodes[v].x += nodes[v].lazy;
        if (nodes[v].l) {
            nodes[nodes[v].l].lazy += nodes[v].lazy;
        }
        if (nodes[v].r) {
            nodes[nodes[v].r].lazy += nodes[v].lazy;
        }
        nodes[v].lazy = 0;
    }
}

struct Treap {
    ll root = 0;

    ll merge(ll l, ll r) {
        push(l), push(r);
        if (!l) {
            return r;
        }
        if (!r) {
            return l;
        }
        if (nodes[l].y > nodes[r].y) {
            nodes[l].r = merge(nodes[l].r, r);
            upd(l);
            return l;
        } else {
            nodes[r].l = merge(l, nodes[r].l);
            upd(r);
            return r;
        }
    }

    Pair split(ll v, ll k) {
        if (!v) {
            return {0, 0};
        }
        push(v);
        if (vsize(nodes[v].l) + 1 <= k) {
            Pair q = split(nodes[v].r, k - vsize(nodes[v].l) - 1);
            nodes[v].r = q.first;
            upd(v);
            return {v, q.second};
        } else {
            Pair q = split(nodes[v].l, k);
            nodes[v].l = q.second;
            upd(v);
            return {q.first, v};
        }
    }

    ll get(ll v, ll k) {
        push(v);
        if (k == vsize(nodes[v].l) + 1) {
            return nodes[v].x;
        } else if (k < vsize(nodes[v].l) + 1) {
            return get(nodes[v].l, k);
        } else {
            return get(nodes[v].r, k - vsize(nodes[v].l) - 1);
        }
    }

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

    void insert(ll x) {
        nodes[CUR] = Node(x);
        root = merge(root, CUR++);
    }

    void insert(ll k, ll x) {  // after first k
        Pair q = split(root, k);
        nodes[CUR] = Node(x);
        root = merge(merge(q.first, CUR++), 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);
        nodes[q.first].lazy -= x;
        nodes[q.second].lazy += x;
        root = merge(q.first, q.second);
    }
};


void solve() {
    CUR = 1;
    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;
        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';
        }
    }
}