#include <bits/stdc++.h>
using namespace std;
int main(){
int n;
int k;
cin >> n >> k;
vector<vector<int>> dp(k+1,vector<int>(n+1,1e9));
vector<int> lis={};
for (int i=0;i<n;i++){
int unos;
cin >> unos;
lis.push_back(unos);
}
dp[0][0]=0;
for (int i=0;i<k;i++){
stack<pair<int,int>> monsta={};
stack<pair<int,int>> monsta2={};
for (int j=0;j<n;j++){
// cout << i << " " << j << "\n";
int sad=lis[j];
int najm=dp[i][j];
while (monsta.size()>0 && monsta.top().first<sad){
najm=min(najm,monsta.top().second);
if (monsta2.size()>0 && monsta2.top().first==monsta.top().first){
monsta2.pop();
}
monsta.pop();
}
if (monsta2.size()==0 || najm+sad<monsta2.top().second){
monsta2.push({sad,najm+sad});
}
monsta.push({sad,najm});
dp[i+1][j+1]=monsta2.top().second;
}
}
cout << dp[k][n] << "\n";
}
