program flow20;
const maxn=300;
maxe=5000;
type lin=record
u,v,w,c,pre:longint;
end;
var
e:array[0..maxe]of lin;
que,d,low,pre,last:array[0..maxn]of longint;
v:array[0..maxn]of boolean;
cost,p,q,a,b,tot:longint;
function calc(i,j:longint):longint;
begin
exit(i*(q+1)+j+2);
end;
function min(a,b:longint):longint;
begin
if a<b then exit(a) else exit(b);
end;
procedure addedge(u,v,w,c:longint);
begin
inc(tot);
e[tot].u:=u;
e[tot].v:=v;
e[tot].w:=w;
e[tot].c:=c;
e[tot].pre:=last[u];
last[u]:=tot;
inc(tot);
e[tot].u:=v;
e[tot].v:=u;
e[tot].w:=0;
e[tot].c:=-c;
e[tot].pre:=last[v];
last[v]:=tot;
end;
function spfa(s,t:longint):boolean;
var l,r,u,tmp,aug:longint;
begin
fillchar(que,sizeof(que),0);
fillchar(d,sizeof(d),254);
fillchar(low,sizeof(low),0);
fillchar(pre,sizeof(pre),0);
fillchar(v,sizeof(v),false);
l:=0;r:=1;que[l]:=s;
d[s]:=0;v[s]:=true;
low[s]:=maxlongint;
low[t]:=low[s];
while l<>r do
begin
u:=que[l];
tmp:=last[u];
while tmp<>-1 do
begin
if (d[e[tmp].v]<d[u]+e[tmp].c)and(e[tmp].w>0) then
begin
d[e[tmp].v]:=d[u]+e[tmp].c;
pre[e[tmp].v]:=tmp;
low[e[tmp].v]:=min(low[u],e[tmp].w);
if not v[e[tmp].v] then
begin
que[r]:=e[tmp].v;
r:=(r+1)mod maxn;
v[e[tmp].v]:=true;
end;
end;
tmp:=e[tmp].pre;
end;
v[u]:=false;
l:=(l+1)mod maxn;
end;
if low[t]=maxlongint then exit(false);
cost:=cost+d[t]*low[t];
u:=t;aug:=low[t];
while u<>s do
begin
dec(e[pre[u]].w,aug);
inc(e[pre[u] xor 1].w,aug);
u:=e[pre[u]].u;
end;
exit(true);
end;
procedure init;
var i,j,k,u,x,y,r,t:longint;
begin
read(a,b);
read(p,q);
tot:=-1;
t:=(p+1)*(q+1)+2;
fillchar(last,sizeof(last),255);
for i:=0 to p do
for j:=1 to q do
begin
read(k);
u:=calc(i,j-1);
if k=0 then addedge(u,u+1,1 shl 20,0)
else begin
addedge(u,u+1,1 shl 20,0);
addedge(u,u+1,1,k);
end;
end;
for i:=0 to q do
for j:=1 to p do
begin
read(k);
u:=calc(j-1,i);
if k=0 then addedge(u,u+q+1,1 shl 1,0)
else begin
addedge(u,u+q+1,1 shl 20,0);
addedge(u,u+q+1,1,k);
end;
end;
for i:=1 to a do
begin
read(r,x,y);
u:=calc(x,y);
addedge(0,u,r,0);
end;
for i:=1 to b do
begin
read(r,x,y);
u:=calc(x,y);
addedge(u,t,r,0);
end;
cost:=0;
while spfa(0,t) do;
writeln(cost);
end;
begin
init;
end.
评论