记录编号	24390	评测结果	AAAAAAAAAAAA
题目名称	[网络流24题] 餐巾	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	0.177 s
提交时间	2011-04-06 16:16:39	内存使用	0.15 MiB

{餐巾
 SPFA最小费用最大流
 Author: yangbohua
 Time: 2011-04-06}
 
program napkin;
const
  maxn=210;

type
  node=record
    v,c,w,next:longint;
  end;

var
  list,path,diste:array[0..maxn*2] of longint;
  map:array[0..maxn*12] of node;
  n,e,p,a,day1,day2,cost1,cost2,cost,ans,flow,i,min:longint;

procedure addedge(i,j,c,w:longint);
begin
  inc(e);
  map[e].v:=j;
  map[e].c:=c;
  map[e].w:=w;
  map[e].next:=list[i];
  list[i]:=e;

  inc(e);
  map[e].v:=i;
  map[e].c:=0;
  map[e].w:=-w;
  map[e].next:=list[j];
  list[j]:=e;
end;

function spfa(var cost:longint):boolean;
var
  dist,q:array[0..maxn*2] of longint;
  b,bb:array[0..maxn*2] of boolean;
  h,t,u,i,j:longint;
begin
  fillchar(dist,sizeof(dist),0);
  fillchar(bb,sizeof(bb),false);
  fillchar(b,sizeof(b),false);
  h:=0;
  t:=1;
  q[1]:=0;
  b[0]:=true;
  bb[0]:=true;
  dist[0]:=0;
  while h<>t do
  begin
    h:=(h mod (n+2))+1;
    i:=q[h];
    u:=list[i];
    while u<>0 do
    begin
      if map[u].c>0 then
      begin
        j:=map[u].v;
        if (dist[i]+map[u].w<dist[j]) or (not bb[j]) then
        begin
          dist[j]:=dist[i]+map[u].w;
          bb[j]:=true;
          diste[j]:=u;
          path[j]:=i;
          if not b[j] then
          begin
            b[j]:=true;
            t:=(t mod (n+2))+1;
            q[t]:=j;
          end
        end;
      end;
      u:=map[u].next;
    end;
    b[i]:=false;
  end;
  spfa:=bb[n+1];
  cost:=dist[n+1];
end;

begin
  assign(input,'napkin.in');
  reset(input);
  assign(output,'napkin.out');
  rewrite(output);

  readln(n);
  e:=0;
  for i:=1 to n do
  begin
    read(a);
    addedge(0,i,a,0);
    addedge(n+i,2*n+1,a,0);
  end;
  readln(p,day1,cost1,day2,cost2);
  for i:=1 to n do
  begin
    addedge(0,n+i,maxlongint,p);
    if i+day1<=n then addedge(i,n+i+day1,maxlongint,cost1);
    if i+day2<=n then addedge(i,n+i+day2,maxlongint,cost2);
    if i+1<=n then addedge(i,i+1,maxlongint,0);
  end;

  ans:=0;
  n:=n*2;
  while spfa(cost) do
  begin
    i:=n+1;
    flow:=maxlongint;
    while i<>0 do
    begin
      if map[diste[i]].c<flow then flow:=map[diste[i]].c;
      i:=path[i];
    end;
    ans:=ans+cost*flow;
    i:=n+1;
    while i<>0 do
    begin
      dec(map[diste[i]].c,flow);
      if diste[i] and 1=1
        then inc(map[diste[i]+1].c,flow)
        else inc(map[diste[i]-1].c,flow);
      i:=path[i];
    end;
  end;

  writeln(ans);
  close(input);
  close(output);
end.