Description
Input
Output
仅包含一个整数，表示可以获得的最大能源收入。注意，你也可以选择不进行任何攻击，这样能源收入为0。
Sample Input
3 2
10 0
20 0
-10 0
-5 1 0 0
100 1 2 1
100 0
Sample Output
25
HINT
在样例中, 植物P1,1可以攻击位置(0,0), P2, 0可以攻击位置(2,1)。
一个方案为，首先进攻P1,1, P0,1，此时可以攻击P0,0 。共得到能源收益为(-5)+20+10 = 25。注意, 位置(2,1)被植物P2,0保护，所以无法攻击第2行中的任何植物。
【大致数据规模】
约20%的数据满足1 ≤ N, M ≤ 5；
约40%的数据满足1 ≤ N, M ≤ 10；
约100%的数据满足1 ≤ N ≤ 20，1 ≤ M ≤ 30，-10000 ≤ Score ≤ 10000 。
详情请见胡伯涛《最小割模型在信息学竞赛中的应用》中最大权闭合图
但是有一点不同，因为有些点不能取，所以我们首先拓扑一下，把有用的点选出来，然后再跑最小割
const
maxn=;
maxm=;
inf=;
var
d,a,first,q:array[..maxn*maxm]of longint;
next,last:array[..maxn*maxm*maxn*maxm]of longint;
map:array[..maxn*maxm,..maxn*maxm]of longint;
n,m,tot,sum,cnt:longint; function calc(i,j:longint):longint;
begin
exit(i*m+j+);
end; procedure insert(x,y:longint);
begin
inc(tot);
last[tot]:=y;
next[tot]:=first[x];
first[x]:=tot;
inc(d[y]);
end; procedure init;
var
i,j,k,l,r,x,y:longint;
begin
read(n,m);
for i:= to n- do
for j:= to m- do
begin
read(a[calc(i,j)]);
read(k);
if j> then insert(calc(i,j),calc(i,j-));
for l:= to k do
begin
read(x,y);
insert(calc(i,j),calc(x,y));
end;
end;
l:=;r:=;
for i:= to n -1do
if d[calc(i,m-)]= then
begin
inc(r);
q[r]:=calc(i,m-);
end;
while l<=r do
begin
if a[q[l]]> then inc(sum,a[q[l]]);
if a[q[l]]> then inc(map[,q[l]],a[q[l]]);
if a[q[l]]< then inc(map[q[l],n*m+],-a[q[l]]);
i:=first[q[l]];
while i<> do
begin
dec(d[last[i]]);inc(map[last[i],q[l]],inf);
if d[last[i]]= then
begin
inc(r);
q[r]:=last[i];
end;
i:=next[i];
end;
inc(l);
end;
cnt:=r;
end; var
dis,vh,his,pre:array[..maxn*maxm]of longint;
flow:longint; procedure sap;
var
i,j,aug,min:longint;
flag:boolean;
begin
vh[]:=cnt+;
i:=;aug:=inf;
while dis[i]<n*m+ do
begin
his[i]:=aug;
flag:=false;
for j:= to n*m+ do
if (map[i,j]>) and (dis[i]=dis[j]+) then
begin
flag:=true;
if aug>map[i,j] then aug:=map[i,j];
pre[j]:=i;
i:=j;
if i=n*m+ then
begin
inc(flow,aug);
while i<> do
begin
inc(map[i,pre[i]],aug);
dec(map[pre[i],i],aug);
i:=pre[i];
end;
aug:=inf;
end;
break;
end;
if flag then continue;
min:=n*m+;
for j:= to n*m+ do
if (map[i,j]>) and (dis[j]<min) then min:=dis[j];
dec(vh[dis[i]]);
if vh[dis[i]]= then break;
dis[i]:=min+;
inc(vh[min+]);
if i<> then
begin
i:=pre[i];
aug:=his[i];
end;
end;
writeln(sum-flow);
end; begin
init;
sap;
end.