萌新白丝萝莉

#include <cstdio>
#include <iostream>
#include <algorithm>
#define ll long long
#define lson p << 1
#define rson p << 1 | 1
using namespace std;
const int N = 1e6 + 5;

int n;
ll C, a[N], lsh[N];

struct node {
	int l, r;
	ll mn, lazy1, lazy2, lazy3;
} t[N << 3];
void pushup(int p) {t[p].mn = min(t[lson].mn, t[rson].mn);}
void build(int p, int l, int r) {
	t[p].l = l, t[p].r = r;
	t[p].lazy1 = -1;
	if (l == r) return;
	int mid = l + r >> 1;
	build(lson, l, mid), build(rson, mid + 1, r);
}
void tag1(int p, ll d) {
	t[p].mn = d;
	t[p].lazy1 = d;
	t[p].lazy2 = t[p].lazy3 = 0;
}
void tag2(int p, ll d) {
	t[p].mn += d;
	t[p].lazy2 += d;
}
void tag3(int p, ll d) {
	t[p].mn += d * lsh[t[p].l];
	t[p].lazy3 += d;
}
void pushdown(int p) {
	if (t[p].lazy1 != -1) {
		tag1(lson, t[p].lazy1), tag1(rson, t[p].lazy1);
		t[p].lazy1 = -1;
	}
	if (t[p].lazy2) {
		tag2(lson, t[p].lazy2), tag2(rson, t[p].lazy2);
		t[p].lazy2 = 0;
	}
	if (t[p].lazy3) {
		tag3(lson, t[p].lazy3), tag3(rson, t[p].lazy3);
		t[p].lazy3 = 0;
	}
}
void upd1(int p, int l, int r, ll d) {
	if (l <= t[p].l && r >= t[p].r) return tag1(p, d), void();
	pushdown(p);
	int mid = t[p].l + t[p].r >> 1;
	if (l <= mid) upd1(lson, l, r, d);
	if (r > mid) upd1(rson, l, r, d);
	pushup(p);
}
void upd2(int p, int l, int r, ll d) {
	if (l > r) return;
	if (l <= t[p].l && r >= t[p].r) return tag2(p, d), void();
	pushdown(p);
	int mid = t[p].l + t[p].r >> 1;
	if (l <= mid) upd2(lson, l, r, d);
	if (r > mid) upd2(rson, l, r, d);
	pushup(p);
}
void upd3(int p, int l, int r, ll d) {
	if (l > r) return;
	if (l <= t[p].l && r >= t[p].r) return tag3(p, d), void();
	pushdown(p);
	int mid = t[p].l + t[p].r >> 1;
	if (l <= mid) upd3(lson, l, r, d);
	if (r > mid) upd3(rson, l, r, d);
	pushup(p);
}
ll query(int p, int x) {
	if (t[p].l == t[p].r) return t[p].mn;
	pushdown(p);
	int mid = t[p].l + t[p].r >> 1;
	if (x <= mid) return query(lson, x);
	return query(rson, x);
}
int find(int p, ll x) {
	if (t[p].mn > x) return -1;
	if (t[p].l == t[p].r) return t[p].l;
	pushdown(p);
	if (t[rson].mn <= x) return find(rson, x);
	return find(lson, x);
}

int main() {
	scanf("%d %lld", &n, &C);
	for (int i = 1; i <= n; i++) scanf("%lld", &a[i]), lsh[i] = a[i];
	sort(lsh + 1, lsh + 1 + n);
	build(1, 1, n);
	for (int i = 1; i <= n; i++) {
		int pos = lower_bound(lsh + 1, lsh + 1 + n, a[i]) - lsh;
		upd2(1, pos, n, -a[i]), upd3(1, pos, n, 1);
		ll val = query(1, pos);
		int p = find(1, val - C);
		if (p != -1) upd2(1, 1, p, C);
		upd1(1, p == -1 ? 1 : p + 1, pos - 1, val);
	}
	printf("%lld", t[1].mn);
	return 0;
}