一开始YY了一种连边方式，就是源点向第一个点连边，第一个点向最后一个点连边，每个边的流量是1，希望能通过一些奇奇怪怪的约束条件来保证能从1跑到n。
但是很快这个想法就被枪毙了——每一天需要消耗的人力是不同的。
怎么办呢？
我们可以考虑一种（我瞎取名叫）替换法的建模方法。
具体来说就是，先确定一个最大流，然后将其中的一些流量替换为必须要通过实际需要的路径才能跑过，这样就保证了答案的合法性。
#include<iostream>
#include<cstdio>
#include<queue>
const int INF = 0x3f3f3f3f;
inline int Min(int A,int B){
return A<B?A:B;
}
inline int Max(int A,int B){
return A>B?A:B;
}
struct ee{
int v;
int w;
int c;
int nxt;
}e[400005];
int h[20005],et=-1;
inline void Eadd(int U,int V,int W,int C){
e[++et]=(ee){V,W,C,h[U]};
h[U]=et;
}
inline void add(int U,int V,int W,int C){
Eadd(U,V,W,C);
Eadd(V,U,0,-C);
}
int n,m,s,t,vis[20005],dis[20005],val[20005],nw[20005],fa[20005];
std::queue<int> q;
inline bool SPFA(){
for(int i=1;i<=t;++i){
vis[i]=0,dis[i]=INF,val[i]=INF;
}
dis[s]=0,vis[s]=1,fa[t]=-1;
q.push(s);
int p;
while(!q.empty()){
p=q.front();
q.pop();
vis[p]=0;
for(int i=h[p];i>=0;i=e[i].nxt){
if(e[i].w>0&&dis[e[i].v]>dis[p]+e[i].c){
dis[e[i].v]=dis[p]+e[i].c;
fa[e[i].v]=p;
nw[e[i].v]=i;
val[e[i].v]=Min(e[i].w,val[p]);
if(!vis[e[i].v]){
vis[e[i].v]=1;
q.push(e[i].v);
}
}
}
}
return fa[t]!=-1;
}
long long ans=0,ans2=0;
inline void EK(){
int p;
while(SPFA()){
p=t;
ans2+=val[t];
ans+=val[t]*dis[t];
while(p!=s){
e[nw[p]].w-=val[t];
e[nw[p]^1].w+=val[t];
p=fa[p];
}
}
}
int a[20005],tot=0;
//tot不能想当然地取最大值，而应该取和。
//这是因为，过程中可能存在一些情况，使得先雇佣某个志愿者会更优。
void init(){
scanf("%d%d",&n,&m);
s=n+2,t=n+3;
for(int i=1;i<=t;++i){
h[i]=-1;
}
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
tot+=a[i];
}
++tot;
add(s,1,tot,0),add(n+1,t,tot,0);
for(int i=1;i<=n;++i){
add(i,i+1,tot-a[i],0);
}
int l,r,c;
for(int i=1;i<=m;++i){
scanf("%d%d%d",&l,&r,&c);
add(l,r+1,tot,c);
}
EK();
printf("%lld\n",ans);
}
int main(){
init();
return 0;
}