
// #pragma GCC optmize("Ofast")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()

typedef long long ll;
typedef long double ld;

template <typename T>
void sort(T &s) {
    sort(all(s));
}

template<typename T>
void rsort(T &s) {
    sort(rall(s));
}

const int inf = 2e9 + 2000;
const ll infll = 2e18 + 2000;
const int R = (1 << 20);
mt19937 rnd(26);

template <typename T>
struct point {
    T x, y;
    point(T x, T y) : x(x), y(y) {}
    point(point a, point b) : x(b.x - a.x), y(b.y - a.y) {}

    point operator + (point &o) const {
        return {x + o.x, y + o.y};
    }

    point operator * (const T k) const {
        return {x * k, y * k};
    }

    T operator * (const point &o) const {
        return x * o.x + y * o.y;
    }

    T operator % (const point &o) const {
        return x * o.y - y * o.x;
    }

    T len2() {
        return x * x + y * y;
    }

    ld len() {
        return sqrt(x * x + y * y);
    }
};



void solve() {
    int n, m;
    cin >> n >> m;

    vector<ll> x(m);
    for (auto &i : x) {
        cin >> i;
    }

    if (n * m > 4000000) {
        if (m <= n) {
            cout << m * x[0] << "\n";
        } else {
            cout << n * x[0] - ((m - n) % 2) * x[0] << "\n";
        }
    }

    reverse(all(x));

    vector<vector<ll> > dp(m + 1, vector<ll> (n + 1, -infll));
    dp[0][0] = 0;
    for (int i = 1; i <= m; ++i) {
        dp[i][1] = max(dp[i][1], dp[i - 1][0] + x[i - 1]);
        dp[i][n - 1] = max(dp[i][n - 1], dp[i - 1][n] - x[i - 1]);

        for (int j = 1; j < n; ++j) {
            dp[i][j - 1] = max(dp[i][j - 1], dp[i - 1][j] - x[i - 1]);
            dp[i][j + 1] = max(dp[i][j + 1], dp[i - 1][j] + x[i - 1]);
        }
    }

    cout << *max_element(all(dp[m])) << "\n";
}


signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int tt = 1;
    cin >> tt;

    while (tt--) {
        solve();
    }
}
