#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define FastIO ios_base::sync_with_stdio(0);cin.tie(nullptr);
#define MULTEST int tt;cin >> tt;while (tt--) solve();
int n,k,arr[100009];
namespace sub2 {
bool check() {
return n <= 20;
}
void solve() {
long long ret = 1e18;
for (int mask = 0;mask < (1 << (n - 1));mask++) if (__builtin_popcount(mask) == k - 1) {
long long curr = 0;
int maxval = arr[1];
for (int i = 0;i < n - 1;i++) {
if (mask >> i & 1) {
curr += maxval;
maxval = arr[i + 2];
} else maxval = max(maxval,arr[i + 2]);
}
curr += maxval;
ret = min(ret,curr);
}
cout << ret;
}
}
namespace sub13 {
bool check() {
return n <= 100;
}
long long dp[109][109];
void solve() {
for (int i = 1;i <= k;i++) dp[0][i] = 1e18;
for (int i = 1;i <= n;i++) {
dp[i][0] = 1e18;
for (int j = 1;j <= k;j++) {
dp[i][j] = 1e18;
int maxval = -1e9;
for (int d = i;d >= 1;d--) {
maxval = max(maxval,arr[d]);
dp[i][j] = min(dp[i][j],dp[d - 1][j - 1] + maxval);
}
}
}
cout << dp[n][k];
}
}
namespace sub4 {
bool check() {
return 1;
}
long long prev[100009],dp[100009];
stack <pair<int,long long>> st;
void solve() {
for (int i = 1;i <= n;i++) {
dp[i] = max(dp[i - 1],1ll*arr[i]);
}
dp[0] = 1e18;
arr[0] = 1e9;
for (int tt = 2;tt <= k;tt++) {
while (st.size()) st.pop();
st.push({0,1e18});
for (int i = 0;i <= n;i++) prev[i] = dp[i],dp[i] = 1e18;
for (int i = 1;i <= n;i++) {
pair <int,long long> hien = {i,prev[i]};
long long val = 1e18;
while (arr[st.top().first] <= arr[i]) {
hien.second = min(hien.second,st.top().second);
val = min(val,st.top().second);
st.pop();
}
val = min(val,prev[st.top().first]);
dp[i] = min(val + arr[i],dp[st.top().first]);
st.push(hien);
}
}
cout << dp[n];
}
}
int main() {
FastIO
// MULTEST
// freopen("blocks.inp","r",stdin);
// freopen("blocks.out","w",stdout);
cin >> n >> k;
for (int i = 1;i <= n;i++) cin >> arr[i];
if (sub2::check()) {
sub2::solve();
return 0;
}
if (sub13::check()) {
sub13::solve();
return 0;
}
if (sub4::check()) {
sub4::solve();
return 0;
}
}
/*
Nho doi vai em gay
co gai ay ngoi duoi goc pho nen tho ...
*/
