#include <bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while (t != 0) {
        int n, m;
        cin >> n >> m;
        vector<long long> a(m);
        long long maxi = -1e9, mini = 1e9, cnt = 0;
        for (int i = 0; i < m; i++) {
            cin >> a[i];
            maxi = max(a[i], maxi);
            mini = min(a[i], mini);
        }
        for (int i = 0; i < cnt; i++) {
            if (a[i] == maxi) {
                cnt++;
            }
        }
        if (n <= cnt) {
            long long ans = maxi * (m - 1);
            cnt -= (m - 1);
            if ((n - m + 1) % 2 == 0) {
                long long temp = m - 1;
                int fl = 1;
                for (int j = 0; j < m; j++) {
                    fl = 1 - fl;
                    if ((temp > 0 && a[j] == maxi && !fl) || (a[j] == maxi && cnt == 0)) {
                        temp--;
                        continue;
                    } else {
                        if (a[j] == maxi) {
                            cnt--;
                        }
                        if (fl) {
                            ans += a[j];
                        } else {
                            ans -= a[j];
                        }
                    }
                }
            }  else {
                long long temp = m - 1;
                int fl = 0;
                for (int j = 0; j < m; j++) {
                    fl = 1 - fl;
                    if ((temp > 0 && a[j] == maxi && !fl) || (a[j] == maxi && cnt == 0)) {
                        temp--;
                        continue;
                    } else {
                        if (a[j] == maxi) {
                            cnt--;
                        }
                        if (fl) {
                            ans += a[j];
                        } else {
                            ans -= a[j];
                        }
                    }
                }
            }
            cout << ans << "\n";
        } else {
            n -= cnt;
            long long ans = maxi * cnt + min(n, m) * mini;
            cnt = m - min(n, m) + 1;
            ans -= mini;
            if (cnt % 2 != 0) {
                ans += mini;
            }
            cout << ans << "\n";
        }
        t--;
    }
}



