#include <bits/stdc++.h>
#define int long long
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(),x.end()
using namespace std;
const int N=5e3+5;
int dp[N][N],x[N][N];
signed main(){
int n,k;
cin>>n>>k;
vector <int> a(n);
for(int i=0;i<n;i++)cin>>a[i];
for(int i=0;i<k;i++){
for(int j=0;j<n;j++){
x[i][j]=1e9;
}
}
for(int i=0;i<n;i++){
dp[0][i]=a[i]+1-a[0];
if(i-1>=0 && i+1<n)x[0][i]=min(x[0][i-1],dp[0][i]-a[i+1]);
else if(i==0 && i+1<n)x[0][i]=dp[0][i]-a[i+1];
}
for(int i=1;i<k;i++){
for(int j=0;j<n;j++){
if(j-1>=0)dp[i][j]=a[j]+1+x[i-1][j-1];
if(j-1>=0 && j+1<n){
x[i][j]=min(x[i][j-1],dp[i][j]-a[j+1]);
}
}
}
cout<<dp[k-1][n-1];
}
