#include <algorithm>
#include <vector>
#include <iostream>
#include <cassert>
#include <tuple>
#include <cmath>
#include <fstream>
using namespace std;

class LineSolver {
public:
    LineSolver() = default;
    LineSolver(const int _K, const vector<int>& _height) 
        : N((int)_height.size()), 
          K(_K), 
          height(_height), 
          pointer(N), 
          tree(N + 1), 
          dp(N + 1),
          stk(N + 1) {
    }

    long long solve_row() {
        int N = (int)height.size();
        long long answer = 0;
        
        for (int _ = 0; _ < 2; _++) {
            for (vector<int>& adj: tree)
                adj.clear();

            for (int i = 0; i < N; ++i) {
                int j = i - 1;
                while (j >= 0 && height[i] <= height[j])
                    j = pointer[j];
                pointer[i] = j;

                if (j == -1)
                    j = N;
                tree[j].push_back(i);
            }
            
            answer = max(answer, compute_dp(N));
            reverse(height.begin(), height.end());
        }       
        return answer;
    }
private:
    struct Line {
        long long a, b;

        Line(long long _a = 0, long long _b = 0)
                : a(_a), b(_b) {
        }

        long long eval(int x) const {
            return a * x + b;
        }

        friend bool is_before(const Line& l1, const Line& l2, const Line& l3) {
            return (l2.b - l1.b) / (l1.a - l2.a) >= (l3.b - l2.b) / (l2.a - l3.a);
        }
    };

    int N, K;
    vector<int> height;
    vector<int> pointer;
    vector< vector<int> > tree;
    vector<long long> dp;
    vector<Line> stk;

    long long compute_dp(int root) {                   
        fill(dp.begin(), dp.end(), 0);
        for (int i = 1; i <= K; ++i) {
            for (const int& son : tree[root]) {
                dfs(son);        
            }
        }
        return *max_element(dp.begin(), dp.end());
    }
    
    int cht_insert(const Line& l, int stk_size) {
        int left = -1, right = stk_size - 1;
        while (right - left > 1) {
            int middle = (left + right) / 2;
            const Line& l1 = stk[middle];
            const Line& l2 = stk[middle + 1];

            if (is_before(l1, l2, l))
                right = middle;
            else
                left = middle;
        }
        return right + 1;
    }

    long long cht_search(int x, int stk_size) {
        int left = -1, right = stk_size - 1;
        while (right - left > 1) {
            int middle = (left + right) / 2;
            if (stk[middle].eval(x) >= stk[middle + 1].eval(x))
                right = middle;
            else
                left = middle;
        }
        return stk[right].eval(x);
    }

    void dfs(int node, int stk_size = 0) {
        long long dp_cost = (pointer[node] == -1) ? 0 : dp[pointer[node]];
        Line new_line(height[node], dp_cost - (long long)pointer[node] * height[node]);
        
        int where = cht_insert(new_line, stk_size); 
        Line aux = stk[where];
        stk[where] = new_line;
        
        for (const int& son: tree[node]) 
            dfs(son, where + 1);
        
        dp[node] = max(dp[node], cht_search(node, where + 1));
        stk[where] = aux;
    }
};

int main() {
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    int T; cin >> T;
    while (T--) {
        int N, K; cin >> N >> K;
        vector<int> height(N);
        for (int i = 0; i < N; ++i)
            cin >> height[i];
        LineSolver solver(K + 1, height);
        cout << solver.solve_row() << '\n';
    }
}