考虑费用流。
你如果直接对于每个面包分别考虑的话，会导致一个问题：面包多不是利润就大。
但流量不用面包也没其他办法了。我们考虑严格控制流量，保证你这个流量无论如何都是一样的，只是把不选的设成代价为 0。
酱紫的话你其实就可以直接搞了，你考虑就是每一次连一个区间，然后每一次再限流就可以了。
连一个区间你如果线段树建图边数会带个 log，时间卡的紧，完全不可接受。
但我们网络流还线段树建图实在是太蠢了。我们网络流有自己的区间覆盖方法！
一般套路都是把限制一条链穿起来然后每一次区间只要连几条边就行啦！
对于这个题你可以先假定我们预定满了蛋糕订单，然后实在做不出来就赔钱！
然后你考虑你要赔的最少。于是你就在赔钱和请人来做里面选，这个就可以费用流啦！
但注意你要严格控制流量所以要在开头和结尾加个限流的，否则亏死了。
另外 EK 太慢啦！用原始对偶哟！
cin >> n >> m >> d;
init();
rep (i, 1, n) cin >> a[i];
int ans = 0;
rep (i, 1, n) {add_edge(i, i + 1, a[i], d);add_edge(i, i + 1, m - a[i], 0);ans += a[i] * d;
}
rep (i, 1, m) {int l, r, c;cin >> l >> r >> c;add_edge(l, r + 1, 1, c);
}
add_edge(n + 2, 1, m, 0);
add_edge(n + 1, n + 3, m, 0);
auto [f, c] = Flow::PrimalDual(n + 2, n + 3);
cout << ans - c << endl;