#include <bits/stdc++.h>
using namespace std;
template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl
using ll = long long;
const int maxn = 100000 + 10;
const ll inf = 1e10;
int n,k;
ll a[maxn];
ll dp[102][maxn];
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin>>n>>k;
for (int i=1; i<=n; i++) {
cin>>a[i];
}
for (int i=1; i<=n; i++) {
dp[1][i]=max(a[i],dp[1][i-1]);
}
for (int j=2; j<=k; j++) {
stack<pair<int,ll>> stk;
for (int i=j; i<=n; i++) {
ll mindp = dp[j-1][i-1];
while (!stk.empty() && a[stk.top().first] <= a[i]) {
mindp = min(mindp, stk.top().second);
stk.pop();
}
dp[j][i] = min(mindp+a[i], stk.empty() ? inf : dp[j][stk.top().first]);
stk.push({i,mindp});
}
}
cout<<dp[k][n]<<endl;
return 0;
}
