#include <bits/stdc++.h>
using namespace std;

long long n, k, d, t[3003], pt[3003], fp = 1e9;
pair<long long, long long> dp[3003][3003];

int main() {
        ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
        cin >> n >> k >> d;
        for(int i = 1; i <= n; ++i) {
                cin >> t[i];
        }
        for(int i = 1; i <= n; ++i) {
                pt[i] = pt[i - 1] + t[i];
        }
        for(int j = 1; j <= n; ++j) {
                for(int i = max(1, j - (int)k + 1); i <= j; ++i) {
                        long long ti = i - 1;
                        if(i == 1) ++ti;
                        for(int gk = 1; gk <= min(ti, k); ++gk) {
                                long long ov = max(t[j] - d, dp[i - 1][gk].second) + d, ck = j - i + 1;
                                long long ljda = ov * ck - (pt[j] - pt[i - 1]);
                                if(dp[j][ck].second == 0 || dp[j][ck].first > ljda + dp[i - 1][gk].first) {
                                        dp[j][ck] = make_pair(ljda + dp[i - 1][gk].first, ov);
                                }
                        }
                }
        }
        for(int i = 1; i <= k; ++i) {
                fp = min(fp, dp[n][i].first);
        }
        cout << fp << endl;
}