将每门课等级拆成0，1,2,3...a[i]个点，对每一个等级大于0的点向它低一级连边，权值为0【意思是，若修了level k。则level(0~k)都当做修了】
将输入的边建边，权值为money[i]。
建立根节点，向每一个level 0的点连边，权值为0【由于初始level 0的都修了】
因为题目要求每门课都必须达到最大level，也就是相应图中根节点能到达全部点，问题就变成了求有向图的最小生成树。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
#define INF 0x3FFFFFF
#define MAXN 5555
struct edge
{
int u,v,w;
}e[9999999];
int n,en;
int pre[MAXN],in[MAXN],id[MAXN],vis[MAXN];
void add(int u,int v,int w)
{
e[en].u=u;
e[en].v=v;
e[en++].w=w;
}
int zl(int root ,int vn)
{
int ans=0;
int cnt;
while(1)
{
for(int i=0;i<vn;i++)
in[i]=INF,id[i]=-1,vis[i]=-1;
for(int i=0;i<en;i++)
{
if(in[e[i].v]>e[i].w && e[i].u!=e[i].v)
{
pre[e[i].v]=e[i].u;
in[e[i].v]=e[i].w;
}
}
in[root]=0;
pre[root]=root;
for(int i=0;i<vn;i++)
{
ans+=in[i];
if(in[i]==INF)
return -1;
}
cnt=0;
for(int i=0;i<vn;i++)
{
if(vis[i]==-1)
{
int t=i;
while(vis[t]==-1)
{
vis[t]=i;
t=pre[t];
}
if(vis[t]!=i || t==root) continue;
for(int j=pre[t];j!=t;j=pre[j])
id[j]=cnt;
id[t]=cnt++;
}
}
if(cnt==0) break;
for(int i=0;i<vn;i++)
if(id[i]==-1)
id[i]=cnt++;
for(int i=0;i<en;i++)
{
int u,v;
u=e[i].u;
v=e[i].v;
e[i].u=id[u];
e[i].v=id[v];
e[i].w-=in[v];
}
vn=cnt;
root=id[root];
}
return ans;
}
int a[MAXN],pres[MAXN];
int main()
{
int x,y,b,c,d,m;
while(~scanf("%d%d",&n,&m))
{
if(!n&&!m) break;
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),
pres[i]=pres[i-1]+a[i]+1;
en=0;
int s=0;
int t=pres[n]+1;
for(int i=1;i<=n;i++)
{
for(int id=1;id<=a[i];id++)
{
add(pres[i-1]+id+1,pres[i-1]+id,0);
// printf("%d -> %d
",pres[i-1]+id+1,pres[i-1]+id);
}
add(s,pres[i-1]+1,0);
// printf("%d -> %d
",pres[i-1]+a[i]+1,t);
// printf("%d -> %d
",s,pres[i-1]+1);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d%d",&x,&y,&b,&c,&d);
add(pres[x-1]+y+1,pres[b-1]+c+1,d);
// printf("%d -> %d
",pres[x-1]+y+1,pres[b-1]+c+1);
}
int tmp=zl(0,t);
if(tmp<0) puts("-1");
else printf("%d
",tmp);
}
return 0;
}