题目
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second
#define lson p << 1
#define rson p << 1 | 1
const int maxn = 1e6 + 5, inf = 1e18, maxm = 4e4 + 5;
const int N = 1e6;
const int mod = 1e9 + 7;
// const int mod = 998244353;
//const __int128 mod = 212370440130137957LL;
// int a[1005][1005];
// bool vis[505][505];
int n, m;
int a[maxn];
int b[maxn];
string s;
// struct Node{
// int a, b;
// // int val, id;
// bool operator<(const Node &u)const{
// // if(b - a != u.b - u.a)
// // return b - a > u.b - u.a;//!!!!!!!!!!!!!!!!!!
// // return b < u.b;
// if(b != u.b) return b > u.b;
// return a > u.a;
// }
// }node[maxn];
int f[maxn][11];//f[i][j]表示前i个数,最多赋值j次 的和的最小值
//long long ? maxn ? n? m?
void solve(){
int res = 0;
int k;
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> a[i];
}
for(int i = 0; i <= n; i++){
for(int j = 0; j <= k; j++){
if(i == 0) f[i][j] = 0;
else f[i][j] = inf;
}
}
// f[0][0] = 0;
for(int i = 1; i <= n; i++){
for(int j = 0; j <= k; j++){
int mn = inf;
for(int x = 0; x <= j && i - x >= 1; x++){
int i2 = i - x;
mn = min(mn, a[i2]);//找到a[i2, i]的最小值mn,从mn所在位置往两边赋值,这样就能遍历到所有往左赋值和往右赋值的情况
f[i][j] = min(f[i][j], f[i2 - 1][j - x] + mn * (i - i2 + 1));
}
}
}
cout << f[n][k] << '\n';
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}