Description
申奥成功后，布布经过不懈努力，终于成为奥组委下属公司人力资源部门的主管。布布刚上任就遇到了一个难
题：为即将启动的奥运新项目招募一批短期志愿者。经过估算，这个项目需要N 天才能完成，其中第i 天至少需要
Ai 个人。 布布通过了解得知，一共有M 类志愿者可以招募。其中第i 类可以从第Si 天工作到第Ti 天，招募费用
是每人Ci 元。新官上任三把火，为了出色地完成自己的工作，布布希望用尽量少的费用招募足够的志愿者，但这
并不是他的特长！于是布布找到了你，希望你帮他设计一种最优的招募方案。
Input
第一行包含两个整数N, M，表示完成项目的天数和可以招募的志愿者的种类。 接下来的一行中包含N 个非负
整数，表示每天至少需要的志愿者人数。 接下来的M 行中每行包含三个整数Si, Ti, Ci，含义如上文所述。为了
方便起见，我们可以认为每类志愿者的数量都是无限多的。
Output
仅包含一个整数，表示你所设计的最优方案的总费用。
Sample Input
3 3
2 3 4
1 2 2
2 3 5
3 3 2
2 3 4
1 2 2
2 3 5
3 3 2
Sample Output
14
HINT
1 ≤ N ≤ 1000，1 ≤ M ≤ 10000，题目中其他所涉及的数据均 不超过2^31-1。
Source
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~费用流~
神奇的建图：
根据不等式建图，一共有S，T，以及n+1个中间点，其中1~n是正常天，n+1是增加的点。
1.num=a[i]-a[i-1]，如果num>=0，则add(S,i,inf,0)，否则add(i,T,inf,0)。
2.对于每种志愿者，add(开始时间，结束时间+1,inf,花费）。
3.对于每一天，add(i+1,i,inf,0)。
然后跑费用流就好了~
具体的证明太麻烦了QAQ，有兴趣可以看一下https://www.byvoid.com/zhs/blog/noi-2008-employee~
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define inf 707406378int n,m,a[1005],fi[1005],w[30001],ne[30001],v[30001],cost[30001],cnt,x,y,z,dis[1005],S,T,totcos,las[1005],kk[30001];
bool b[1005];queue<int> q;int read()
{int x=0,f=1;char ch=getchar();while(ch<'0' || ch>'9') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f;
}void add(int u,int vv,int val,int cos)
{w[++cnt]=vv;ne[cnt]=fi[u];fi[u]=cnt;v[cnt]=val;cost[cnt]=cos;kk[cnt]=u;w[++cnt]=u;ne[cnt]=fi[vv];fi[vv]=cnt;v[cnt]=0;cost[cnt]=-cos;kk[cnt]=vv;
}bool findd()
{memset(dis,127/3,sizeof(dis));dis[S]=0;b[S]=1;q.push(S);a[S]=inf;while(!q.empty()){int k=q.front();q.pop();for(int i=fi[k];i;i=ne[i])if(v[i]>0 && dis[w[i]]>dis[k]+cost[i]){dis[w[i]]=dis[k]+cost[i];a[w[i]]=min(a[k],v[i]);las[w[i]]=i;if(!b[w[i]]){b[w[i]]=1;q.push(w[i]);}}b[k]=0;}if(dis[T]==inf) return 0;totcos+=a[T]*dis[T];for(int i=T;i!=S;i=kk[las[i]]){v[las[i]]-=a[T];v[las[i]^1]+=a[T];}return 1;
}int main()
{n=read();m=read();T=n+2;cnt=1;for(int i=1;i<=n;i++) a[i]=read();for(int i=n+1;i;i--){a[i]-=a[i-1];if(a[i]<0) add(i,T,-a[i],0);else add(S,i,a[i],0);}for(int i=1;i<=m;i++){x=read();y=read();z=read();add(x,y+1,inf,z);}for(int i=1;i<=n;i++) add(i+1,i,inf,0);while(findd());printf("%d\n",totcos);return 0;
}