#include <iostream>
#include <stdio.h>
#include <deque>
using namespace std;
typedef long long ll;
const int N = 1e5 + 11;
const ll oo = 1e18;
int n,k,lastGreater[N];
ll f[N][101],a[N],minf[N],tmp[N];
deque <int> Q;
void init(){
ll cur = -1;
for(int i = 1; i <= n; ++i){
cur = max(cur,a[i]);
f[i][1] = cur;
}
for(int i = 1; i <= n; ++i){
lastGreater[i] = 0;
while(Q.size() && a[Q.back()] <= a[i]) Q.pop_back();
if(Q.size()) lastGreater[i] = Q.back();
Q.push_back(i);
}
//for(int i = 1; i <= n; ++i) cout << i << " ~> " << lastGreater[i] << endl;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie();
cout.tie();
cin >> n >> k;
for(int i = 1; i <= n; ++i) cin >> a[i];
for(int i = 0; i <= n; ++i)
for(int j = 1; j <= k; ++j) f[i][j] = oo;
init();
minf[0] = oo;
//for(int i = 1; i <= n; ++i) cout << "lastGreater["<<i<<"] = " << lastGreater[i] << endl;
/*for(int i = 1; i <= n; ++i){
cout << "f["<<i<<"][1] = " << f[i][1] << endl;
}*/
for(int j = 2; j <= k; ++j){
Q.clear();
for(int i = 1; i <= n; ++i){
minf[i] = f[i - 1][j - 1]; // minf[i] : from lastGreater[i] -> i - 1
while(Q.size() && a[Q.back()] <= a[i]){
minf[i] = min(minf[i],min(minf[Q.back()],f[Q.back()][j - 1]));
Q.pop_back();
}
//cout << i << " => ["<< (Q.size() ? Q.back() : 0) << " -> " << i - 1<<"] = " << minf[i] << endl;
Q.push_back(i);
}
for(int i = 1; i <= n; ++i) minf[i] += a[i];
for(int i = 1; i <= n; ++i){
f[i][j] = minf[i] = min(minf[i],minf[lastGreater[i]]);
}
/*cout << "j = " << j << " : " << endl;
for(int i = 1; i <= n; ++i) cout << f[i][j] << " / ";
cout << endl;
for(int i = 1; i <= n; ++i) tmp[i] = f[i][j],f[i][j] = oo;
for(int i = 1; i <= n; ++i){
ll cc = 0;
for(int v = i; v > 0; --v){
cc = max(cc,a[v]);
f[i][j] = min(f[i][j],f[v - 1][j - 1] + cc);
}
if(f[i][j] != tmp[i]){
cout << "ok at f["<<i<<","<<j<<"] = " << f[i][j] << endl;
}
}
for(int i = 1; i <= n; ++i) cout << f[i][j] << " / ";
cout << endl << endl;*/
}
cout << f[n][k];
return 0;
}
