记录编号	20473	评测结果	AAAAAAAAAA
题目名称	罪犯问题B	最终得分	100
用户昵称	maxiem	是否通过	通过
代码语言	Pascal	运行时间	1.409 s
提交时间	2010-10-26 10:39:48	内存使用	1.31 MiB

program criminalb;
var
  a,b,c:array [1..1000] of longint;
  cut,max,min:array [0..1,0..50000] of longint;
  fc:array [1..50000] of boolean;
  ct,top,ansmax,ansmin,maxx,last,now,i,j,k,n,m,t,l:longint;
begin
  fillchar (c,sizeof(c),0);
  fillchar (b,sizeof(b),0);
  fillchar (a,sizeof(a),0);
  fillchar (cut,sizeof(cut),0);
  fillchar (fc,sizeof(fc),0);
  fillchar (max,sizeof(max),0);
  filldword (min,sizeof(min) div 4,200000000);
  assign (input,'criminalb.in');
  reset (input);
  readln (n,m,k);
  for i:=1 to n do read (c[i]);
  for i:=1 to m do begin
    readln (t);
	if t>0 then inc(a[t]) else inc(b[-t]);
  end;
  close (input);
  assign (output,'criminalb.out');
  rewrite (output);
  max[0,b[1]]:=c[1];
  cut[0,0]:=2;
  cut[0,1]:=b[1];
  cut[0,2]:=a[1];
  now:=1;last:=0;
  for i:=2 to n do begin
    cut[now,0]:=0;
	fillchar (fc,sizeof(fc),false);
    for j:=1 to cut[last,0] do begin
	  if (cut[last,j]+a[i]<=k) then begin
	    if max[now,cut[last,j]+a[i]]<max[last,cut[last,j]] then begin
		  max[now,cut[last,j]+a[i]]:=max[last,cut[last,j]];
		  if fc[cut[last,j]+a[i]]=false then begin
		    inc(cut[now,0]);
                        cut[now,cut[now,0]]:=cut[last,j]+a[i];
			fc[cut[last,j]+a[i]]:=true;
		  end;
	end;
            end;
   if (cut[last,j]+b[i]<=k) then begin
            if max[now,cut[last,j]+b[i]]<max[last,cut[last,j]]+c[i] then begin
                  max[now,cut[last,j]+b[i]]:=max[last,cut[last,j]]+c[i];
		  if fc[cut[last,j]+b[i]]=false then begin
		    inc(cut[now,0]);
                        cut[now,cut[now,0]]:=cut[last,j]+b[i];
			fc[cut[last,j]+b[i]]:=true;
		  end;
		end;
	  end;
	end;
	for j:=1 to cut[last,0] do max[last,cut[last,j]]:=0;
	last:=(last+1) mod 2;
	now:=(now+1) mod 2;
  end;
  ansmax:=0;
  for i:=0 to k do if ansmax<max[last,i] then ansmax:=max[last,i];
  fillchar (cut,sizeof(cut),0);
  min[0,b[1]]:=c[1];
  min[0,a[1]]:=0;
  cut[0,0]:=2;
  cut[0,1]:=b[1];
  cut[0,2]:=a[1];
  now:=1;last:=0;
  for i:=2 to n do begin
    cut[now,0]:=0;
	fillchar (fc,sizeof(fc),false);
    for j:=1 to cut[last,0] do begin
          if (cut[last,j]+a[i]<=k) then begin
	    if min[now,cut[last,j]+a[i]]>min[last,cut[last,j]] then begin
		  min[now,cut[last,j]+a[i]]:=min[last,cut[last,j]];
		  if fc[cut[last,j]+a[i]]=false then begin
		    inc(cut[now,0]);
			cut[now,cut[now,0]]:=cut[last,j]+a[i];
			fc[cut[last,j]+a[i]]:=true;
		  end;
		end;
          end;
          if (cut[last,j]+b[i]<=k) then begin
            if min[now,cut[last,j]+b[i]]>min[last,cut[last,j]]+c[i] then begin
                  min[now,cut[last,j]+b[i]]:=min[last,cut[last,j]]+c[i];
		  if fc[cut[last,j]+b[i]]=false then begin
		    inc(cut[now,0]);
                        cut[now,cut[now,0]]:=cut[last,j]+b[i];
			fc[cut[last,j]+b[i]]:=true;
		  end;
		end;
	  end;
	end;
	for j:=1 to cut[last,0] do min[last,cut[last,j]]:=2000000000;
	last:=(last+1) mod 2;
	now:=(now+1) mod 2;
  end;
  ansmin:=maxlongint;
  for i:=0 to k do if min[last,i]<ansmin then ansmin:=min[last,i];
  writeln (ansmax);
  writeln (ansmin);
  close (output);
end.