记录编号	20165	评测结果	AAAAAAAAAA
题目名称	罪犯问题B	最终得分	100
用户昵称	Achilles	是否通过	通过
代码语言	Pascal	运行时间	1.568 s
提交时间	2010-10-21 15:42:02	内存使用	0.93 MiB

program criminalb;
var
  temp,n,m,k,i,j,now,last:longint;
  a:array[1..1000]of longint;
  sz:array[1..1000,1..2]of longint;
  ans,cut:array[0..1,0..50000]of longint;
  hx:array[1..50000]of boolean;
begin
  assign(input,'criminalb.in');
  assign(output,'criminalb.out');
  reset(input);
  rewrite(output);
  readln(n,m,k);
  for i:=1 to n do
    read(a[i]);
  readln;
  fillchar(sz,sizeof(sz),0);
  for i:=1 to m do
  begin
    readln(temp);
    if temp>0 then sz[temp,1]:=sz[temp,1]+1 else sz[-temp,2]:=sz[-temp,2]+1;
  end;
  fillchar(ans,sizeof(ans),0);
  fillchar(cut,sizeof(cut),0);
  ans[0,sz[1,2]]:=a[1];
  cut[0,0]:=2;
  cut[0,1]:=sz[1,2];
  cut[0,2]:=sz[1,1];
  now:=1;
  last:=0;
  for i:=2 to n do
  begin
    cut[now,0]:=0;
    fillchar(hx,sizeof(hx),true);
    for j:=1 to cut[last,0] do
    begin
      if cut[last,j]+sz[i,1]<=k then begin
        if ans[last,cut[last,j]]>=ans[now,cut[last,j]+sz[i,1]] then begin
          ans[now,cut[last,j]+sz[i,1]]:=ans[last,cut[last,j]];
          if hx[cut[last,j]+sz[i,1]] then begin
            hx[cut[last,j]+sz[i,1]]:=false;
            cut[now,0]:=cut[now,0]+1;
            cut[now,cut[now,0]]:=cut[last,j]+sz[i,1];
          end;
        end;
      end;
      if cut[last,j]+sz[i,2]<=k then begin
        if ans[last,cut[last,j]]+a[i]>=ans[now,cut[last,j]+sz[i,2]] then begin
          ans[now,cut[last,j]+sz[i,2]]:=ans[last,cut[last,j]]+a[i];
          if hx[cut[last,j]+sz[i,2]] then begin
            hx[cut[last,j]+sz[i,2]]:=false;
            cut[now,0]:=cut[now,0]+1;
            cut[now,cut[now,0]]:=cut[last,j]+sz[i,2];
          end;
        end;
      end;
    end;
    for j:=1 to cut[last,0] do
      ans[last,cut[last,j]]:=0;
    now:=(now+1)mod 2;
    last:=(last+1)mod 2;
  end;
  temp:=0;
  for i:=0 to k do
    if ans[last,i]>temp then temp:=ans[last,i];
  writeln(temp);
  for i:=0 to 1 do
    for j:=0 to k do
      ans[i,j]:=200000000;
  fillchar(cut,sizeof(cut),0);
  ans[0,sz[1,2]]:=a[1];
  ans[0,sz[1,1]]:=0;
  cut[0,0]:=2;
  cut[0,1]:=sz[1,2];
  cut[0,2]:=sz[1,1];
  now:=1;
  last:=0;
  for i:=2 to n do
  begin
    cut[now,0]:=0;
    fillchar(hx,sizeof(hx),true);
    for j:=1 to cut[last,0] do
    begin
      if cut[last,j]+sz[i,1]<=k then begin
        if ans[last,cut[last,j]]<=ans[now,cut[last,j]+sz[i,1]] then begin
          ans[now,cut[last,j]+sz[i,1]]:=ans[last,cut[last,j]];
          if hx[cut[last,j]+sz[i,1]] then begin
            hx[cut[last,j]+sz[i,1]]:=false;
            cut[now,0]:=cut[now,0]+1;
            cut[now,cut[now,0]]:=cut[last,j]+sz[i,1];
          end;
        end;
      end;
      if cut[last,j]+sz[i,2]<=k then begin
        if ans[last,cut[last,j]]+a[i]<=ans[now,cut[last,j]+sz[i,2]] then begin
          ans[now,cut[last,j]+sz[i,2]]:=ans[last,cut[last,j]]+a[i];
          if hx[cut[last,j]+sz[i,2]] then begin
            hx[cut[last,j]+sz[i,2]]:=false;
            cut[now,0]:=cut[now,0]+1;
            cut[now,cut[now,0]]:=cut[last,j]+sz[i,2];
          end;
        end;
      end;
    end;
    for j:=1 to cut[last,0] do
      ans[last,cut[last,j]]:=200000000;
    now:=(now+1)mod 2;
    last:=(last+1)mod 2;
  end;
  temp:=200000000;
  for i:=0 to k do
    if ans[last,i]<temp then temp:=ans[last,i];
  writeln(temp);
  close(input);
  close(output);
end.