对与区间有关的建模不够熟悉，即使想到了根据面包师建模，也难以建出东西来。

需要对这方面加以训练。

题意：

有 天， 个面包师，第 个面包师需要花 元雇佣，雇佣过后，他会在第 到第 天，每天给你生产一个面包。

每天有个预期销售量 ，如果你当天产出了 个面包，你实际只能卖出 个面包。

卖出一个面包可以获得 元的收益。现在你是面包铺老板，请最大化自己的收益。

。

对面包建模是比较寄的。

那不妨根据面包师建模。

先把答案取反，变成最小费用模型。

尝试建边 代表每一天的情况，因为这一天卖 个面包，每个可以带来 的贡献，溢出的则没贡献，所以建边 。

对于一个面包师，建边 ，那么这就是一个循环流模型。我们每次增广一个圈，就相当于选择了一个面包师。

注意到边有负权，我们使用带负权的最小费用流 即可完成计算。

因为这张图非常特殊，每个点连向 与连向 的边的数量是相等的，所以我们甚至不需要虚拟源汇，直接以 为源点， 为汇点跑就可以了。

所以我们总共只需要建出三类边：

注意： 本题在新图中需要保证流量不超过 ，因为在新图中有可能增广出大于 的流量，但这些东西是对应不回原来的流量意义的。

因为这题 稍大，需要 的原始对偶算法方可通过（我写了但被卡常乐），所以我最终使用的是 AtCoder Library 自带的费用流，跑得很快。

#include <bits/stdc++.h>
#include <atcoder/mincostflow>
#pragma GCC optimize(3)
using namespace std;
typedef long long ll;
const ll llinf = 0x3f3f3f3f3f3f3f3f;
int n,m,D;
ll ans;
int main()
{
	cin >> n >> m >> D;
	atcoder::mcf_graph<ll,ll> G(n+2);

	for(int i = 1;i <= n;i++)
	{
		int a;
		cin >> a;
		G.add_edge(i,i + 1,a,D);
		G.add_edge(i,i + 1,m - a,0);
		ans += 1ll * D * a;
	}
	for(int i = 1;i <= m;i++)
	{
		int l,r,c;
		cin >> l >> r >> c;
		G.add_edge(l,r + 1,1,c);
	}
	cout << ans - G.flow(1,n + 1,m).second << endl;
	return 0;
}