提交记录

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define MAXM 400005
#define INF 2147483647
template <typename T> inline void read(T& x) {
	x=0;T 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^48),ch=getchar();
	x=x*f;
	return;
}
template <typename T,typename ...Arg>void read(T& x,Arg& ...arg){
	read(x);
	read(arg...);
}
template <typename T>void write(T x) {
	if(x<0)putchar('-'),x=-x;
	if(x<10)putchar(x+'0');
	else write(x/10),putchar(x%10+'0');
}
template <typename T,typename ...Arg>void write(T& x,Arg& ...arg){
	write(x);
	putchar(' ');
	write(arg...);
}
int n,m,s,t,ans,user,point;
struct Edge{
	int t,v,sl;
}edge[MAXM];
int head[MAXM],tail[MAXN],now[MAXN];
int cc[MAXN],sum;
inline void input(int x,int y,int z){
	edge[m].t=y;
	edge[m].v=z;
	edge[m].sl=z;
    head[m]=tail[x];
    tail[x]=m;
    m++;
	edge[m].t=x;
	edge[m].v=z;
	edge[m].sl=0;
    head[m]=tail[y];
    tail[y]=m;
    m++;
	return;
}
inline bool bfs(){
	memset(cc,-1,sizeof(cc));
	queue<int>q;
	q.push(s);
	cc[s]=0;
    now[s]=tail[s];
	while(!q.empty()){
		int tp=q.front();
		q.pop();
        for(int i=tail[tp];i!=-1;i=head[i]){
			int tt=edge[i].t;
			if(cc[tt]!=-1||edge[i].sl<=0) continue;
			cc[tt]=cc[tp]+1;
            now[tt]=tail[tt];
			q.push(tt);
            if(tt==t) return 1;
		}
	}
	return 0;
}
inline int dfs(int x,int in){
	if(x==t) return in;
	int sum=0;
    for(int i=now[x];i!=-1;i=head[i]){ 
        now[x]=i;   
		int tt=edge[i].t;
		if(edge[i].sl>0&&cc[tt]==cc[x]+1){
			int k=dfs(tt,min(in,edge[i].sl));
			if(!k) cc[tt]=-1;
			edge[i].sl-=k;
			edge[i^1].sl+=k;
			sum+=k;
			in-=k;
		}
	}
	return sum;
}
signed main(){
    // freopen("P4174_9.in","r",stdin);
    memset(tail,-1,sizeof(tail));
    memset(head,-1,sizeof(head));
    s=0;t=1,point=2;
    read(n,user);
    for(int i=0;i<n;i++,point++){
        int p;
        read(p);
        input(point,t,p);
    }
    for(int i=0;i<user;i++,point++){
        int a,b,c;
        read(a,b,c);
        input(s,point,c);
        sum+=c;
        input(point,a+1,INF);
        input(point,b+1,INF);
    }
    while(bfs()) ans+=dfs(s,INF);
    write(sum-ans);
	return 0;
}