//Dedicated to my love, ivaziva
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
#define DBG(x) cout << #x << "= " << x << "\n"
const int mxN=1e5;
const ll inf=(ll)(1e18);
ll n, k;
ll a[mxN], dp[mxN][105];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for(ll i=1; i<=n; ++i) cin >> a[i];
for(ll i=0; i<=n; ++i) {
for(ll j=0; j<=k; ++j) dp[i][j]=inf;
}
ll mx=a[1];
for(ll i=1; i<=n; ++i) {
mx=max(mx, a[i]);
dp[i][1]=mx;
}
for(ll j=2; j<=k; ++j) {
stack<ar<ll, 2>> stk;
for(ll i=1; i<=n; ++i) {
ll upd=dp[i-1][j-1];
while(!stk.empty()&&stk.top()[0]<a[i]) {
upd=min(upd, stk.top()[1]);
stk.pop();
}
if(stk.empty() || a[i]+upd<stk.top()[0]+stk.top()[1]) {
stk.push({a[i], upd});
}
if(j>i) continue;
dp[i][j]=stk.top()[0]+stk.top()[1];
}
}
cout << dp[n][k] << "\n";
return 0;
}
