#include <bits/stdc++.h>
using namespace std;
// #define int long long
const int M = 5005;
signed main()
{
int n,m;
cin>>n>>m;
int a[n];
for (int i=0;i<n;i++)
cin>>a[i];
int dp[n][M];
for (int i=0;i<M;i++)
dp[0][i]=n+1;
for (int i=0;i<=m;i++)
dp[0][i]=(a[0]!=i);
for (int i=1;i<n;i++)
{
int suf[M];suf[M-1]=dp[i-1][M-1];
for (int j=M-2;j>=0;j--)
suf[j]=min(suf[j+1],dp[i-1][j]);
for (int j=0;j<M;j++)
dp[i][j]=suf[max(0,j-m)]+(a[i]!=j);
}
int ans=dp[n-1][0];
for (int i=0;i<M;i++)
ans=min(ans,dp[n-1][i]);
cout<<ans<<endl;
return 0;
}
