玄关求条

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+5,inf=1<<30;
int cnt=1,head[N],dep[N],gap[N],liu[N];
//        前向星  深度          流量 
int maxflow;
int n,m,s,t,nn,yuan,shen;
struct Node{
    int u,v,w;
}node[250005];
inline void addedge(int u,int v,int w){
    node[++cnt].v=v;
    node[cnt].w=w;
    node[cnt].u=head[u];
    head[u]=cnt;
	node[++cnt].v=u;
	node[cnt].w=0;
	node[cnt].u=head[v];
	head[v]=cnt;
}
void bfs(){
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    dep[t]=0;
    gap[0]=1;
    queue<int>q;
    q.push(t);
    while(!q.empty()){
        int u=q.front();
        q.pop();
        for(int i=head[u];i;i=node[i].u){
            int v=node[i].v;
            if(dep[v]!=-1)continue;
            q.push(v);
            dep[v]=dep[u]+1;
            gap[dep[v]]++;
        }
    }
    return;
}
int dfs(int u,int flow){
    if(u==t){
        maxflow+=flow;
        return flow;
    }
    int used=0;
    for(int i=head[u];i;i=node[i].u){
        int d=node[i].v;
        if(node[i].w&&dep[d]+1==dep[u]){
            int mi=dfs(d,min(node[i].w,flow-used));
            if(mi){
                node[i].w-=mi;
                node[i^1].w+=mi;
                used+=mi;
            }
            if(used==flow)return used;
        }
    }
    --gap[dep[u]];
    if(gap[dep[u]]==0)dep[s]=n+1;
    dep[u]++;
    gap[dep[u]]++;
    return used; 
}
long long ISAP(){
    maxflow=0;
    bfs();
    while(dep[s]<nn)dfs(s,inf);
    return maxflow;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	while(cin>>n>>m){
		memset(node,0,sizeof node);
		memset(liu,0,sizeof liu);
		yuan=1,shen=n+m+2,nn=n+m+2;		
		for(int i=2;i<=m+1;++i){	
			int G;
			cin>>G;
			addedge(s,i,inf-G);	
			liu[i]+=G;
			liu[s]-=G;
		}
		for(int i=m+2;i<=m+n+1;++i){	
			int C,D;
			cin>>C>>D;
			addedge(i,t,D);
			for(int j=1;j<=C;++j){		
				int T,L,R;		
				cin>>T>>L>>R;
				T+=2;		
				addedge(T,i,R-L);	
				liu[T]-=L;			 
				liu[i]+=L; 
			}
		}
		s=0,t=n+m+3;		
		int outflow=0;		
		for(int i=1;i<=nn;++i){		
			if(liu[i]>0){
				addedge(yuan,i,liu[i]);
				outflow+=liu[i]; 
			}else if(liu[i]<0)addedge(i,shen,-liu[i]);
		}
		addedge(t,s,inf);		
		if(ISAP()<outflow)cout<<"-1\n\n";		
		else{
			int res=node[cnt-1].w;		
			node[cnt-1].w=node[cnt-2].w=0;	
			s=yuan,t=shen;		
			cout<<res+ISAP()<<"\n\n"; 		
		}
	}
	return 0;
}