#include <bits/stdc++.h>
#include <ext/random>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pb push_back
#define ppb pop_back
#define fr first
#define sc second
#define all(v) v.begin(), v.end()
#define vektor vector
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
constexpr ull Mod = 1e9 + 7;
constexpr ull sqr = 547;
constexpr ld eps = 1e-9;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll l, ll r) {if(l <= r) return uniform_int_distribution <ll> (l, r)(rng); return -1;}
void solve(){
ll n, k;
cin >> n >> k;
vector <ll> a(n + 1);
vector <vector <pair <ll, ll>>> dp(n + 1, vector <pair <ll, ll>> (2));
for(int i = 1; i <= n; i ++) cin >> a[i];
ll l = 0, r = 1e9 * n, ans = 1e9 * n;
while(l <= r){
ll mid = (l + r) >> 1;
dp[1][0] = {0, 0};
dp[1][1] = {a[1] - mid, 1};
for(int i = 2; i <= n; i ++){
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = max({make_pair(dp[i - 1][0].fr + a[i] - mid, dp[i - 1][0].sc + 1), make_pair(dp[i - 1][1].fr + a[i], dp[i - 1][1].sc), make_pair(dp[i - 1][1].fr + a[i] - mid, dp[i - 1][1].sc + 1)});
dp[i][1] = max(dp[i][1], {a[i] - mid, 1});
}
if(max(dp[n][0], dp[n][1]).sc > k) l = mid + 1;
else r = mid - 1, ans = mid;
// cout << max(dp[n][0], dp[n][1]).sc << " " << mid << " " << ans << "\n";
}
dp[1][0] = {0, 0};
dp[1][1] = {a[1] - ans, 1};
for(int i = 2; i <= n; i ++){
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = max({make_pair(dp[i - 1][0].fr + a[i] - ans, dp[i - 1][0].sc + 1), make_pair(dp[i - 1][1].fr + a[i], dp[i - 1][1].sc), make_pair(dp[i - 1][1].fr + a[i] - ans, dp[i - 1][1].sc + 1)});
dp[i][1] = max(dp[i][1], {a[i] - ans, 1});
}
cout << max(dp[n][0], dp[n][1]).fr + ans * k;
}
main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if(fopen("COUNTSEQ.inp", "r")){
freopen("COUNTSEQ.inp", "r", stdin);
freopen("COUNTSEQ.out", "w", stdout);
}
int t = 1;
cin >> t;
while(t --){
solve();
cout << "\n";
}
}
