https://codeforces.com/contest/1969/problem/C

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
typedef vector<long long> VI;
#define int long long
#define INF 0x3f3f3f3f
#define endl '\n'
#define N 300010
const int mod = 1e9 + 7;

ll ksm(ll a, ll b) {
    ll ans = 1;
    for (; b; b >>= 1LL) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
    }
    return ans;
}
ll lowbit(ll x) {
    return -x & x;
}

int p[N], si[N];
int find(int x) {
    if (x == p[x])return p[x];
    p[x] = find(p[x]);
    return p[x];
}
//size[find(b)] += size[find(a)];
//p[find(a)] = find(b);

vector<int> a(N);
int dp[N][11];

//dp[i][j] 表示前i个数使用j次的最小和
//dp[j][j] = min(dp[i - 1][j], dp[i - k  - 1][j - k] + min(a[i - k - 1] ~ a[i]) * (k  + 1))

void solve() {
    int n, k;
    cin >> n >> k;

    for (int i = 1; i <= n; i++)cin >> a[i];
    for (int i = 1; i <= n ; i ++) {
        for (int j = 0; j <= k; j++) {
            dp[i][j] = 1e18;
        }
    }

    for (int i = 1; i <= n; i ++) {
        for (int j = 0; j <= k ; j ++) {
            dp[i][j] = dp[i - 1][j] + a[i];

            int mn = a[i];

            for (int kk = 1; kk <= j && kk < i; kk++) { //从当前位置枚举使用1 ~ k种的方案， 找最小值
                mn = min(a[i - kk], mn);

                dp[i][j] = min(dp[i][j], dp[i - kk - 1][j - kk] + (kk + 1) * mn);
            }
        }
    }


    cout << dp[n][k] << endl;






}


signed main() {

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
    cin >> T;
    while (T --)

        solve();

    return 0;
}