这道题还是比较简单的费用流,由于w是递增的
实际上,这题数据还可以强一点,比如说分段函数不保证费用递增,
就要加一点技巧了(要保证函数的顺序)
const inf=;
type node=record
next,point,flow,cost:longint;
end;
var q:array[..] of longint;
edge:array[..] of node;
v:array[..] of boolean;
p,time,c,d,pre:array[..] of longint;
len,i,j,n,m,t,total,s,w,x:longint;
ans:int64; procedure add(x,y,f,w:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].flow:=f;
edge[len].cost:=w;
edge[len].next:=p[x];
p[x]:=len;
end; function spfa:boolean;
var i,j,f,r,x,y:longint;
begin
fillchar(v,sizeof(v),false);
v[]:=true;
for i:= to t do
d[i]:=inf;
d[]:=;
f:=;
r:=;
q[]:=;
while f<=r do
begin
x:=q[f];
v[x]:=false;
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if edge[i].flow> then
if d[y]>d[x]+edge[i].cost then
begin
d[y]:=d[x]+edge[i].cost;
pre[y]:=i;
time[y]:=x;
if not v[y] then
begin
v[y]:=true;
inc(r);
q[r]:=y;
end;
end;
i:=edge[i].next;
end;
inc(f);
end;
if d[t]=inf then exit(false) else exit(true);
end; procedure mincost;
var i,j,x,y,neck:longint;
begin
while spfa do
begin
neck:=inf;
i:=t;
while i<> do
begin
j:=pre[i];
if neck>edge[j].flow then neck:=edge[j].flow;
i:=time[i];
end;
i:=t;
while i<> do
begin
j:=pre[i];
dec(edge[j].flow,neck);
inc(edge[j xor ].flow,neck);
i:=time[i];
end;
ans:=ans+neck*d[t];
end;
end; begin
readln(n,m);
len:=-;
fillchar(p,sizeof(p),);
for i:= to m do
begin
read(c[i]);
add(,i,c[i],);
add(i,,,);
end;
for i:= to n do
begin
for j:= to m do
begin
read(x);
if x= then
begin
add(j,i+m,c[j],);
add(i+m,j,,);
end;
end;
end;
t:=n+m+;
for i:= to n do
begin
readln(s);
fillchar(time,sizeof(time),);
for j:= to s do
read(time[j]);
for j:= to s do
begin
read(w);
add(i+m,t,time[j]-time[j-],w);
add(t,i+m,,-w);
end;
read(w);
add(i+m,t,inf,w);
add(t,i+m,,-w);
end;
mincost;
writeln(ans);
end.