OK

#include <bits/stdc++.h>

#define ll long long
#define M 2000000000000000ll

using namespace std;
const int N = 3020;

int n, d;

ll A[N][N];
ll B[N][N];
ll a[N], S[N];
ll t, answer, sv;

int main()
{
  scanf("%d %d %lld", &n, &d, &t); d = min(n, d);
  for(int i = 1; i <= n; ++ i)
  {
    scanf("%lld", &a[i]);
    sv += max(0ll, t - a[i]);
    a[i] = max(a[i], t);
    S[i] = S[i - 1] + a[i];
  }
  A[n][n] = 0;
  for(int i = n - 1; i >= 1; -- i)
  {
    for(int j = i + 1; j <= min(i + d - 1, n); ++ j)
      A[i][j] = A[i + 1][j] + a[j] - a[i];
    ll now = a[i];
    int cap = 0;
    ll tot = 0; A[i][i] = M;
    for(int j = i + 1; j <= n; ++ j)
    {
      int l, r;
      l = j; r = min(j + d - 1, n);
      while(l < r)
      {
        int mid = (l + r) / 2;
        if(a[mid] - t >= now)
          r = mid;
        else
          l = mid + 1;
      }
      if(l <= min(j + d - 1, n) && a[l] - t >= now)
          A[i][i] = min(A[i][i], tot + B[j][l]);
      if(cap == 0)
        now += t, cap = d;
      if(now < a[j])
      {
        now += ((a[j] - now + 1) / t + 1 ) * t;
        cap = d;
      }
      cap --;
      tot += now - a[j];
    }
    A[i][i] = min(A[i][i], tot);
    B[i][min(i + d - 1, n)] = A[i][min(i + d - 1, n)];
    for(int j = min(i + d - 1, n) - 1; j >= i; -- j)
      B[i][j] = min(B[i][j + 1], A[i][j]);
  }
  answer = M;
  for(int j = 1; j <= min(d, n); ++ j)
    answer = min(answer, A[1][j]);
  printf("%lld\n", answer + sv);
}