#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
const int maxk=105, maxn=1e5+5;
const int inf=1e9;
vector < pair < int, int > > v[maxk];
vector < int > valu[maxk];
int dp[maxn][maxk];
int a[maxn];
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n, k;
cin >> n >> k;
for(int i=0; i<n; i++){
cin >> a[i];
}
int sum=0;
for(int i=0; i<k; i++){
v[i].push_back({sum, a[i]});
valu[i].push_back(sum+a[i]);
sum+=a[i];
dp[i][i]=sum;
}
int maksi=0;
for(int i=0; i<n; i++){
maksi=max(maksi, a[i]);
dp[i][0]=maksi;
}
int mindp;
int val;
for(int i=0; i<n; i++){
for(int j=1; j<min(k, i); j++){
mindp=dp[i-1][j-1];
val=a[i];
while(!v[j].empty() && v[j].back().second<=val){
mindp=min(mindp, v[j].back().first);
v[j].pop_back();
valu[j].pop_back();
}
if(!valu[j].empty()){
valu[j].push_back(min(valu[j].back(), val+mindp));
}
else{
valu[j].push_back(val+mindp);
}
dp[i][j]=valu[j].back();
v[j].push_back({mindp, val});
}
}
/* for(int i=0; i<k; i++){
for(int j=0; j<n; j++){
cout << dp[j][i] << ' ';
}
cout << '\n';
}*/
cout << dp[n-1][k-1] << '\n';
return 0;
}
