记录编号	19940	评测结果	AAAAAAAAAA
题目名称	罪犯问题B	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	1.824 s
提交时间	2010-10-19 14:01:54	内存使用	0.31 MiB

program criminalb;
var
  f:array[0..50000] of longint;
  c1,c2,w:array[0..1000] of longint;
  ans,n,m,k,i,j,r,sum,h,tmp:longint;

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

  readln(n,m,k);
  fillchar(c1,sizeof(c1),0);
  fillchar(c2,sizeof(c2),0);
  fillchar(w,sizeof(w),0);
  sum:=0;
  for i:=1 to n do
  begin
    read(w[i]);
    sum:=sum+w[i];
  end;
  readln;
  for i:=1 to m do
  begin
    readln(r);
    if r>0
      then inc(c1[r])
      else inc(c2[-r]);
  end;

  for j:=1 to k do
    f[j]:=-99999999;
  f[0]:=0;
  for i:=1 to n do
    for j:=k downto 0 do
    begin
      tmp:=-99999999;
      if (j-c2[i]>=0) and (f[j-c2[i]]>=0)
        then tmp:=f[j-c2[i]]+w[i];
      if (j-c1[i]>=0) and (f[j-c1[i]]>=0) and (f[j-c1[i]]>tmp)
        then tmp:=f[j-c1[i]];
      f[j]:=tmp;
    end;

  ans:=0;
  for i:=0 to k do
    if f[i]>ans then ans:=f[i];
  writeln(ans);

  for j:=1 to k do
    f[j]:=-99999999;
  f[0]:=0;
  for i:=1 to n do
    for j:=k downto 0 do
    begin
      tmp:=-99999999;
      if (j-c1[i]>=0) and (f[j-c1[i]]>=0)
        then tmp:=f[j-c1[i]]+w[i];
      if (j-c2[i]>=0) and (f[j-c2[i]]>=0) and (f[j-c2[i]]>tmp)
        then tmp:=f[j-c2[i]];
      f[j]:=tmp;
    end;

  ans:=0;
  for i:=0 to k do
    if f[i]>ans then ans:=f[i];
  writeln(sum-ans);

  close(input);
  close(output)
end.