46pts 求条

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf=8e18+7;
const int N=450,M=5050;
int ca,cb,n,m,cnt;
int pos[N][N];
int ss,tt;
ll ans;
int h[N],e[M],ne[M],idx;
ll w[M],c[M];
inline void add(int a,int b,ll x,ll y){
	e[idx]=b;
	ne[idx]=h[a];
	w[idx]=x;
	c[idx]=y;
	h[a]=idx++;
}
ll dis[N];
int vis[N],now[N];
inline bool spfa(){
	queue<int> q;
	for(int i=1;i<=cnt+2;i++){
		dis[i]=inf;
		vis[i]=0;
	}
	dis[ss]=0;
	vis[ss]=1;
	q.push(ss);
	while(q.size()){
		int p=q.front();
		vis[p]=0;
		q.pop();
		for(int i=h[p];i!=-1;i=ne[i]){
			int j=e[i];
			if(w[i] && dis[j]>dis[p]+c[i]){
				dis[j]=dis[p]+c[i];
				if(!vis[j]){
					vis[j]=1;
					q.push(j);
				}
			}
		}
	}
	return dis[tt]!=inf;
}
ll dfs(int x,ll su){
	if(x==tt) return su;
	ll res=0;
	vis[x]=1;
	for(int i=now[x];(i!=-1) && su;i=ne[i]){
		int j=e[i];
		now[x]=i;
		if(w[i]>0 && !vis[j] && dis[j]==dis[x]+c[i]){
			ll k=dfs(j,min(su,w[i]));
			res+=k;
			su-=k;
			w[i]-=k;
			w[i^1]+=k;
			ans+=c[i]*k;
		}
	}
	vis[x]=0;
	return res;
}
inline void dinic(){
	while(spfa()){
		for(int i=1;i<=cnt+2;i++) now[i]=h[i];
		while(dfs(ss,inf));
	}
}
int main(){
	memset(h,-1,sizeof h);
	scanf("%d%d",&ca,&cb);
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n+1;i++) for(int j=1;j<=m+1;j++) pos[i][j]=(m+1)*(i-1)+j;
	cnt=(n+1)*(m+1);
	for(int i=1;i<=n+1;i++){
		for(int j=1;j<=m;j++){
			ll x;
			scanf("%lld",&x);
//			printf("%d %d %d %d\n",pos[i][j],pos[i][j+1],1,-x);
			add(pos[i][j],pos[i][j+1],1,-x);
			add(pos[i][j+1],pos[i][j],0,x);
			add(pos[i][j],pos[i][j+1],inf,0);
			add(pos[i][j+1],pos[i][j],0,0);
		}
	}
	for(int j=1;j<=m+1;j++){
		for(int i=1;i<=n;i++){
			ll x;
			scanf("%lld",&x);
//			printf("%d %d %d %d\n",pos[i][j],pos[i+1][j],1,-x);
			add(pos[i][j],pos[i+1][j],1,-x);
			add(pos[i+1][j],pos[i][j],0,x);
			add(pos[i][j],pos[i+1][j],inf,0);
			add(pos[i+1][j],pos[i][j],0,0);
		}
	}
	ss=cnt+1,tt=cnt+2;
	for(int i=1;i<=ca;i++){
		int k,x,y;
		scanf("%d%d%d",&k,&x,&y);
		x++,y++;
		add(ss,pos[x][y],k,0);
		add(pos[x][y],ss,0,0);
	} 
	for(int i=1;i<=cb;i++){
		int k,x,y;
		scanf("%d%d%d",&k,&x,&y);
		x++,y++;
		add(pos[x][y],tt,k,0);
		add(tt,pos[x][y],0,0);
	}
	dinic();
	printf("%lld",-ans);
}