#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int inf = 1e18 + 100;

bool comp(pair<int, int> a, pair<int, int> b) {
    if (a.first == b.first) {
        return a.second > b.second;
    }
    return a.first < b.first;
}


void make_norm(vector<pair<int, int>> & lst) {
    sort(lst.begin(), lst.end(), comp);
    vector<pair<int, int>> res;
    for (int i = 0; i < lst.size(); i++) {
        if (i == 0 || lst[i].first != lst[i - 1].first) {
            res.push_back(lst[i]);
        }
    }
    lst = res;
}


bool comp_optimize(pair<int, int> a, pair<int, int> b) {
    return a.second > b.second;
}

void sol() {
    int n, m;
    cin >> n >> m;
    vector<int> lst(m + 1, 0);
    for (int i = 0; i < m; i++) {
        cin >> lst[i];
    }
    reverse(lst.begin(), lst.end());
    vector<pair<int, int>> dp;
    dp.push_back({n, 0});
    for (int i = 1; i <= m; i++) {
        vector<pair<int, int>> new_dp;
        for (auto pai : dp) {
            int j = pai.first;
            int res = pai.second;
            if (j != 0) {
                new_dp.push_back({j - 1, res + lst[i]});
            }
            if (j != n) {
                new_dp.push_back({j + 1, res - lst[i]});
            }
        }
        make_norm(new_dp);
        dp = new_dp;
        if (n * m > 4e6 && dp.size() > 200) {
            sort(dp.begin(), dp.end(), comp);
            while (dp.size() > 100) {
                dp.pop_back();
            }
        }
    }
    int ans = -inf;
    for (auto pai : dp) {
        ans = max(ans, pai.second);
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(15);
    int t;
    cin >> t;
    for (; t > 0; --t) {
        sol();
    }
}
