记录编号	20037	评测结果	AAAAAAAAAA
题目名称	罪犯问题B	最终得分	100
用户昵称	wo shi 刘畅	是否通过	通过
代码语言	Pascal	运行时间	1.812 s
提交时间	2010-10-19 22:08:51	内存使用	0.59 MiB

var
  n,m,v,i,j,max,t,total,s,now:longint;
  a,b,e:array[0..2000]of longint;
  f,g:array[0..60000]of longint;

begin
  assign(input,'criminalb.in'); reset(input);
  assign(output,'criminalb.out'); rewrite(output);
  readln(n,m,v);
  for i:=1 to n do
  begin
    read(e[i]);
    inc(total,e[i]);
  end;
  for i:=1 to m do
  begin
    readln(s);
    if s>0 then
    inc(a[abs(s)])
    else inc(b[abs(s)]);
  end;

  for i:=1 to v do f[i]:=-maxlongint;
  f[0]:=0;

  for i:=1 to n do
   for j:=v downto 0 do
   begin
     t:=-maxlongint;
     if (j>=b[i])and(f[j-b[i]]>=0) then
     t:=f[j-b[i]]+e[i];

     if (j>=a[i])and(f[j-a[i]]>=0)and(f[j-a[i]]>t) then
     t:=f[j-a[i]];
     f[j]:=t;
   end;

  for i:=0 to v do
  begin
    if f[i]>max then
    max:=f[i];
    f[i]:=-maxlongint;
  end;
  writeln(max);
  f[0]:=0;
  for i:=1 to n do
   for j:=v downto 0 do
   begin
     t:=-maxlongint;
     if (j-a[i]>=0)and(f[j-a[i]]>=0) then
     t:=f[j-a[i]]+e[i];

     if (j-b[i]>=0)and(f[j-b[i]]>=0)and(f[j-b[i]]>t)
     then t:=f[j-b[i]];
     f[j]:=t;
   end;
  max:=0;
  for i:=0 to v do
  if f[i]>max then max:=f[i];
  writeln(total-max);
  close(input);
  close(output);
end.