#include <bits/stdc++.h>
using namespace std;
#define taskname "JOI18_stove"
#define forinc(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define fordec(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
#define foreach(i, x) for (auto &i : x)
#define ms(x, n) memset(x, n, sizeof(x))
#define sz(x) int((x).size())
#define all(x) (x).begin(), (x).end()
#define uni(x) (x).erase(unique(all(x)), (x).end())
#define fi first
#define se second
#define pb push_back
#define pf push_front
template<typename TH>
void _dbg(const char* sdbg, TH h)
{
cerr << sdbg << " = " << h << "\n";
}
template<typename TH, typename... TA>
void _dbg(const char* sdbg, TH h, TA... t)
{
while (*sdbg != ',') cerr << *sdbg++;
cerr << " = " << h << ",";
_dbg(sdbg + 1, t...);
}
#define db(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#define chkpt cerr << "--- Checkpoint here ---\n";
const int N=1e5+5;
const int64_t LINF=1e18;
int n,k,a[N];
int64_t f[5005][5005],g[5005][5005];
void Solve()
{
forinc(i,0,n)
{
forinc(j,0,k)
{
f[i][j]=LINF;
g[i][j]=LINF;
}
}
f[0][0]=0;
forinc(i,1,n)
{
g[i][0]=-a[1];
}
forinc(i,1,n)
{
forinc(j,1,k)
{
if(g[i-1][j-1]!=LINF)
{
f[i][j]=g[i-1][j-1]+a[i]+1;
g[i][j]=min(g[i-1][j],f[i][j]-a[i+1]);
}
}
}
int64_t ans=LINF;
forinc(i,0,k)
{
ans=min(ans,f[n][i]);
}
cout<<ans<<'\n';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
#ifndef ONLINE_JUDGE
// freopen(taskname".INP","r",stdin);
#endif // ONLINE_JUDGE
cin>>n>>k;
forinc(i,1,n)
{
cin>>a[i];
}
Solve();
return 0;
}
