很像最大权闭合子图的题目
s向每个工作连边，流量为收益
每个工序，由工作i向对应机器连边，流量为租用费
每个机器向t连边，流量为购买费
显然跑最小割，ans=总收益-mincut
const inf=;
type node=record
flow,next,point:longint;
end; var edge:array[..] of node;
pre,p,cur,numh,h,d:array[..] of longint;
ans,n,m,j,t,len,a,b,x,y,i:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y,z:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].flow:=z;
edge[len].next:=p[x];
p[x]:=len;
end; function sap:longint;
var tmp,u,i,j,q,neck:longint;
begin
for i:= to t do
cur[i]:=p[i];
numh[]:=t+;
neck:=inf;
u:=;
sap:=;
while h[]<t+ do
begin
d[u]:=neck;
i:=cur[u];
while i<>- do
begin
j:=edge[i].point;
if (edge[i].flow>) and (h[u]=h[j]+) then
begin
pre[j]:=u;
cur[u]:=i;
neck:=min(neck,edge[i].flow);
u:=j;
if u=t then
begin
sap:=sap+neck;
while u<> do
begin
u:=pre[u];
j:=cur[u];
dec(edge[j].flow,neck);
inc(edge[j xor ].flow,neck);
end;
neck:=inf;
end;
break;
end;
i:=edge[i].next;
end;
if i=- then
begin
dec(numh[h[u]]);
if numh[h[u]]= then exit;
q:=-;
tmp:=t;
i:=p[u];
while i<>- do
begin
j:=edge[i].point;
if edge[i].flow> then
if h[j]<tmp then
begin
q:=i;
tmp:=h[j];
end;
i:=edge[i].next;
end;
h[u]:=tmp+;
inc(numh[h[u]]);
cur[u]:=q;
if u<> then
begin
u:=pre[u];
neck:=d[u];
end;
end;
end;
end; begin
len:=-;
fillchar(p,sizeof(p),);
readln(n,m);
t:=n+m+;
for i:= to n do
begin
readln(a,b);
ans:=ans+a;
add(,i,a);
add(i,,);
for j:= to b do
begin
readln(x,y);
add(i,n+x,y);
add(n+x,i,);
end;
end;
for i:= to m do
begin
readln(x);
add(n+i,t,x);
add(t,n+,);
end;
writeln(ans-sap);
end.