记录编号	8431	评测结果	WWWEEEEEEW
题目名称	越狱	最终得分	0
用户昵称	bing	是否通过	未通过
代码语言	Pascal	运行时间	0.179 s
提交时间	2008-11-14 11:38:03	内存使用	0.21 MiB

program bing;
var
 f1,f2:text;
 n,l,p:longint;
 a,b:array[1..10000] of integer;
 f,ft,ftt:array[0..10000] of integer;
procedure init;
var
 i,j:integer;
begin
 assign(f1,'prisonbreak.in');reset(F1);
 assign(f2,'prisonbreak.out');rewrite(f2);
 readln(f1,n);
 for i:=1 to n do readln(f1,a[i],b[i]);
 readln(f1,l,p);
 for i:=0 to l do f[i]:=10001;
 fillchar(ft,sizeof(ft),0);
 for i:=0 to l do ftt[i]:=p;
end;
procedure nb;
var
 i,j:integer;
begin
 for i:=n downto 1 do
 for j:=l-a[i]+ftt[j-b[i]]+b[i] downto l-a[i] do
 if ft[j-b[i]]+1<f[j] then
                       begin
                        f[j]:=ft[j-b[i]]+1;
                        ftt[j]:=ftt[j-b[i]]-(j-b[i])+b[i];
                        ft[j]:=f[j];
                       end;
end;
begin
 init;
 nb;
 if f[l]=10001 then write(f2,'-1')
 else write(f2,f[l]);
 close(f1);close(f2);
end.