#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <cctype>
#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
#include <bitset>
using namespace std;

const int MAXN = 100000;

int a[MAXN];

long long solve(int a[], int n, int k)
{
    vector<int> left(n), right(n);
    for (int i = 0; i < n; ++ i) {
        left[i] = i - 1;
        while (left[i] >= 0 && a[left[i]] >= a[i]) {
            left[i] = left[left[i]];
        }
    }
    for (int i = n - 1; i >= 0; -- i) {
        right[i] = i + 1;
        while (right[i] < n && a[right[i]] >= a[i]) {
            right[i] = right[right[i]];
        }
    }
    vector<vector<long long>> f(n, vector<long long>(k + 1, 0));
    for (int u = 0; u < n; ++ u) {
        // (left[u], u], height = a[u]
        assert(u >= left[u]);
        long long delta_right = (long long)a[u] * (u - left[u]);
        f[u][0] = delta_right;
        for (int v = left[u]; v >= 0; v = left[v]) {
            // (v, left[u]], height = a[v]
            assert(left[u] >= v);
            long long delta_left = (long long)a[v] * (left[u] - v);
            assert(delta_left >= 0 && delta_right >= 0);
            for (int i = 0; i < k; ++ i) {
                f[u][i + 1] = max(f[u][i + 1], delta_left + delta_right + f[v][i]);
            }
        }
    }
    long long ret = 0;
    for (int u = 0; u < n; ++ u) {
        // (u, right[u]), height = a[u]
        long long delta_right = (long long)a[u] * (right[u] - u - 1);
        ret = max(ret, delta_right + *max_element(f[u].begin(), f[u].end()));
    }
    return ret;
}

int main()
{
    int tests, sum_n = 0, sum_k = 0;
    for (assert(scanf("%d", &tests) == 1 && 1 <= tests && tests <= 30); tests --; ) {
        int n, k;
        assert(scanf("%d%d", &n, &k) == 2);
        assert(1 <= n && n <= MAXN);
        assert(0 <= k && k <= MAXN);
        sum_n += n;
        sum_k += k;
        assert(sum_n <= MAXN);
        assert(sum_k <= MAXN);
        for (int i = 0; i < n; ++ i) {
            assert(scanf("%d", &a[i]) == 1);
            assert(0 <= a[i] && a[i] <= MAXN);
        }
        long long ret = solve(a, n, k);
        reverse(a, a + n);
        ret = max(ret, solve(a, n, k));
        printf("%lld\n", ret);
    }
    return 0;
}