C++ :

#include <bits/stdc++.h>
using namespace std;
const int N = 500 +5;
const int M = 100 +5;
const int T = 4000000 +5;
typedef long long ll;
ll n,m,t;
ll a[N];
ll cnt[T],sum[T],f[T]={0};
ll l=1,r,q[T];
inline double getSlope(int u, int v) { return (double) (f[v] + sum[v] - f[u] - sum[u]) / (cnt[u] == cnt[v] ? 1e-9 : cnt[v] - cnt[u]); }
int main()
{
    scanf("%lld%lld",&n,&m);
    for (int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+n+1);
    // 状态压缩
    ll dd=a[1];
    for (int i=1;i<=n;i++)
    {
        a[i]-=dd;
        if (a[i]-a[i-1]>2*m)
        {
            dd+=a[i]-a[i-1]-2*m;
            a[i]=a[i-1]+2*m;
        }
        cnt[a[i]]++;
        sum[a[i]]+=a[i];
    }
    t=a[n];
    // 求前缀和
    for (int i=1;i<=t+m;i++)
        cnt[i]+=cnt[i-1],sum[i]+=sum[i-1];
    // DP
    l=1;r=0;
    for (int i=0;i<=t+m;i++)
    {
        if (i-m>=0)
        {
            while (l<r&&getSlope(q[r-1],q[r])>=getSlope(q[r],i-m)) r--;
            q[++r]=i-m;
        }
        while (l<r&&getSlope(q[l],q[l+1])<=i) l++;
        f[i]=cnt[i]*i-sum[i];  // 边界情况
        if (l<=r) f[i]=min(f[i],f[q[l]]+(cnt[i]-cnt[q[l]])*i-(sum[i]-sum[q[l]]));
    }
    // 求ans
    ll ans=1ll<<62;
    for (int i=t;i<=t+m;i++)
        ans=min(ans,f[i]);
    printf("%lld",ans);
}