#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using li = __int128;
using db = double;
using ld = long double;
using pi = pair <int, int>;
using pll = pair <ll, ll>;
#define all(x) x.begin(), x.end()

const ll INFll = 3e14;

mt19937 rnd(time(NULL));

struct V {
    db x;
    db y;
};

V operator+ (const V& a, const V& b) {
    return {a.x + b.x, a.y + b.y};
}
db operator* (const V& a, const V& b) {
    return a.x * b.x + a.y * b.y;
}
db operator^ (const V& a, const V& b) {
    return a.x * b.y - a.y * b.x;
}
V operator* (const V& a, db k) {
    return {a.x * k, a.y * k};
}

ll bin_pow(ll a, ll s, ll mod) {
    ll res = 1;
    while (s) {
        if (s & 1) {
            res *= a;
            res %= mod;
        }
        a = (a * a) % mod;
        s >>= 1;
    }
    return res;
}


void solve() {
    int n, m;
    cin >> n >> m;
    vector <ll> v(m);
    for (auto& i : v) cin >> i;
    reverse(all(v));
    vector <pair <ll, int>> dp;
    dp.push_back({v[0], 1});
    vector <pair <ll, int>> mp(n + 1);
    for (int i = 1; i < m; ++i) {
        //map <int, ll> mp;
        for (auto [x, j] : dp) {
            if (j - 1 >= 0) {
                if (mp[j - 1].second == i) mp[j - 1] = max(mp[j - 1], {x - v[i], i});
                else mp[j - 1] = {x - v[i], i};
            }
            if (j + 1 <= n) {
                if (mp[j + 1].second == i) mp[j + 1] = max(mp[j + 1], {x + v[i], i});
                else mp[j + 1] = {x + v[i], i};
            }
        }
        dp.clear();
        for (auto [j, x] : mp) dp.push_back({x, j});
        sort(all(dp));
        reverse(all(dp));
        while (dp.size() > 80) dp.pop_back();
    }
    cout << dp.rbegin()->first << '\n';
}


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