#include <cstdio>
#include <cstring>
#include <deque>
#include <algorithm>
using namespace std;
int dp[105][100005];
int a[100005];
int n,k;
int main(){
scanf("%d %d",&n,&k);
int maxv = 0;
memset(dp,0x3f,sizeof(dp));
for (int i=1; i<=n; i++) {
scanf("%d",&a[i]);
maxv = max(maxv,a[i]);
dp[1][i] = maxv;
}
for (int i=2; i<=k; i++) {
deque<int> dq,dq2;
for (int j=1; j<=n; j++) {
int my_dp = dp[i-1][j-1];
while (!dq.empty() && dq.back() < a[j]) {
my_dp = min(my_dp,dq2.back());
dq.pop_back();
dq2.pop_back();
}
if(dq.empty() || my_dp + a[j] < dq.back() + dq2.back()){
dq.push_back(a[j]);
dq2.push_back(my_dp);
}
if(j >= i) dp[i][j] = dq.back() + dq2.back();
}
}
printf("%d",dp[k][n]);
}
