#pragma GCC optimize("O2, Ofast,fast-math,unroll-loops,no-stack-protector,inline")
// #pragma GCC target("avx, avx2")
#include <bits/stdc++.h>

using namespace std;

// #define int long long
// #define map unordered_map
const int M = 290;
const int MXN = 300000;

bool used[MXN + 1];
int arr[MXN];

signed main() {
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    freopen("input.txt", "r", stdin);
    int t;
    cin >> t;
    for (int q = 0; q < t; q++) {
        int n, m;
        cin >> n >> m;
        for (int i = 0; i < m; i++) {
            cin >> arr[i];
        }
        vector<pair<int, long long>> dp;
        dp.push_back({0, 0});
        for (int i = m - 1; i >= 0; i--) {
            int cur = arr[i];
            vector<pair<long long, int>> cur1;
            for (int k = 0; k < dp.size(); k++) {
                int j = dp[k].first;
                long long num = dp[k].second;
                if (j < n) {
                    cur1.push_back({num + cur, j + 1});
                }
                if (j > 0) {
                    cur1.push_back({num - cur, j - 1});
                }
            }
            sort(cur1.rbegin(), cur1.rend());
            int num = 0;
            vector<pair<int, long long>> dp1;
            vector<int> ind;
            for (int j = 0; j < cur1.size() && num < M; j++) {
                if (!used[cur1[j].second]) {
                    used[cur1[j].second] = 1;
                    ind.push_back(cur1[j].second);
                    dp1.push_back({cur1[j].second, cur1[j].first});
                    num++;
                }
            }
            for (int i : ind) {
                used[i] = 0;
            }
            dp = dp1;
        }
        long long mx = -1e18;
        for (auto [j, num] : dp) {
            mx = max(mx, num);
        }
        cout << mx << endl;
    }
}