#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int sz = 203030;
int N, K;
int h[sz];
ll dp[55][sz];
int f[sz], g[sz];
void solvefg() {
  for (int i = 1; i <= N; i++)
    for (f[i] = i - 1; h[f[i]] >= h[i] && f[i] >= 1; f[i] = f[f[i]]);
  for (int i = N; i; i--)
    for (g[i] = i + 1; h[g[i]] >= h[i] && g[i] <= N; g[i] = g[g[i]]);
}

#define next _next
int node[sz], next[sz], to[sz], e;
void ins(int x, int y) {e++; next[e] = node[x]; node[x] = e; to[e] = y;}
void clr() {for (int i = 0; i <= N; i++) node[i] = 0; for (int i = 1; i <= e; i++) next[i] = to[i] = 0; e = 0;}

class line {
public:
  ll k, b;
  line(){}
  line(ll _k, ll _b) {k = _k; b = _b;}
};
line stk[sz];

typedef double LF;
LF crossx(line u, line v) {return ((LF)1.0) * (v.b - u.b) / (u.k - v.k);}

#define ans (a + tn)
ll best(ll x, int top) {
  int a = 1, tn;
  for (tn = 1 << 18; tn; tn >>= 1)
    if (ans <= top && crossx(stk[ans - 1], stk[ans]) < x) a += tn;
  return stk[a].k * x + stk[a].b;
}
int find_pos(line l, int top) {
  int a = 1, tn;
  for (tn = 1 << 18; tn; tn >>= 1)
    if (ans <= top && crossx(stk[ans - 1], stk[ans]) < crossx(stk[ans], l)) a += tn;
  return a;
}
#undef ans

void dfs(int x, int u, int top) {
  dp[x][u] = best(f[u], top) + 1ll * h[u] * (u - f[u]);
  line ins = line(h[u], dp[x - 1][u] - 1ll * h[u] * u);
  int pos = find_pos(ins, top) + 1;
  line tmp = stk[pos]; stk[pos] = ins;
  for (int v = node[u]; v; v = next[v]) dfs(x, to[v], pos);
  stk[pos] = tmp;
}

ll solve() {
  int u, x, v;
  clr(); solvefg();
  for (x = 1; x <= N; x++) ins(f[x], x);
  for (x = 1; x <= N; x++) dp[1][x] = 1ll * h[x] * (x - f[x]);
  for (x = 2; x <= K; x++) dfs(x, 0, 0);
  ll ans = 0;
  for (u = 1; u <= N; u++) ans = max(ans, 1ll * h[u] * (g[u] - u - 1) + dp[K][u]); return ans;
}

int doit() {
  scanf("%d %d", &N, &K); K++;
  for (int i = 1; i <= N; i++) scanf("%d", &h[i]);
  ll ans = solve(); reverse(h + 1, h + N + 1); ans = max(ans, solve());
  cout << ans << endl;
}
int main() {int T; scanf("%d", &T); while (T--) doit(); return 0;}