#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;
#define int long long
using ll = long long;

typedef tree<int, null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int N = 2e3+10, inf = 1e18;
int dp[N][N];
int a[N];

signed main () {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n, m;
        cin >> n >> m;
        dp[m][0] = 0;
        for (int i = 1; i <= n; i++) {
            dp[m][i] = -inf;
        }
        for (int i = 0; i < m; i++) {
            cin >> a[i];
        }
        for (int i = m-1; i >= 0; i--) {
            for (int j = 0; j <= n; j++) {
                dp[i][j] = -inf;
                if (j >= 1) {
                    dp[i][j] = max(dp[i][j], dp[i+1][j-1] + a[i]);
                }
                if (j <= n-1) {
                    dp[i][j] = max(dp[i][j], dp[i+1][j+1] - a[i]);
                }
            }
        }
        int ans = -inf;
        for (int i = 0; i <= n; i++) {
            ans = max(ans, dp[0][i]);
        }
        cout << ans << '\n';
    }
    return 0;
}