记录编号	428163	评测结果	AAAAAAAAAA
题目名称	为了博多	最终得分	100
用户昵称	test	是否通过	通过
代码语言	C++	运行时间	0.217 s
提交时间	2017-07-24 19:59:13	内存使用	6.19 MiB

#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <cstdio>
#include <string>
#include <vector>
#include <cstring>
#include <complex>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#define rg register
#define ll long long
using namespace std;

inline int gi()
{
	rg int r = 0; rg bool b = 1; rg char c = getchar();
	while ((c < '0' || c > '9') && c != '-') c = getchar();
	if (c == '-') b = 0;
	while (c >= '0' && c <= '9') { r = (r << 1) + (r << 3) + c - '0', c = getchar(); }
	if (b) return r; return -r;
}

const int inf = 2147483647, N = 2e4+5, M = 5e5+5;
int n,m,S,T,lay[N],num,f[N];
struct Edge
{
	int to,nx,cap;
}eg[M];
queue <int> q;

inline void add(int x,int y,int z)
{
	eg[++num]=(Edge){y,f[x],z}; f[x]=num;
}

inline void link(int x,int y,int z)
{
	add(x,y,z), add(y,x,0);
}

inline int dfs(rg int o,rg int flow)
{
	rg int i,to,cap,fl,tmp;
	fl=0;
	if (o == T || !flow) return flow;
	for (i=f[o]; i; i=eg[i].nx)
		{
			to=eg[i].to; cap=eg[i].cap;
			if (lay[o] != lay[to]-1 || cap <= 0)
				continue;
			tmp=dfs(to,min(flow,cap));
			fl+=tmp; flow-=tmp;
			eg[i].cap-=tmp; eg[i^1].cap+=tmp;
			if (!flow) break;
		}
	if (!fl) lay[o]=0;
	return fl;
}

inline int bfs()
{
	memset(lay,0,sizeof(lay));
	rg int o,to,cap,i;
	q.push(S); lay[S]=1;
	while (!q.empty())
		{
			o=q.front(); q.pop();
			for (i=f[o]; i; i=eg[i].nx)
				{
					to=eg[i].to; cap=eg[i].cap;
					if (lay[to] || cap <= 0)
						continue;
					lay[to]=lay[o]+1;
					if (to == T)
						{
							while (!q.empty()) q.pop();
							break;
						}
					q.push(to);
				}
		}
	return lay[T];
}

inline int dinic()
{
	rg int flow; flow=0;
	while (bfs())
		flow+=dfs(S,inf);
	return flow;
}

int main()
{
	freopen("hakata.in","r",stdin);
	freopen("hakata.out","w",stdout);
	rg int i,ans,x,y,bf;
	n=gi(), m=gi();
	ans=S=0, T=n+1, num=1;
	for (i=1; i<=n; ++i)
		{
			bf=gi(); ans+=bf;
			link(S,i,bf);
			bf=gi(); ans+=bf;
			link(i,T,bf);
		}
	for (i=1; i<=m; ++i)
		{
			x=gi(), y=gi(), bf=gi();
			ans+=bf;
			add(x,y,bf), add(y,x,bf);
		}
	printf("%d\n",ans-dinic());
	return 0;
}