记录编号	8443	评测结果	AWWWWAWWAA
题目名称	越狱	最终得分	40
用户昵称	elysian	是否通过	未通过
代码语言	Pascal	运行时间	0.038 s
提交时间	2008-11-14 12:25:02	内存使用	0.34 MiB

program elysian;
const
fin='prisonbreak.in';fout='prisonbreak.out';
var
f,p:array[0..10005,0..1] of longint;
d,a:array[0..10005] of longint;
f1,f2:text;
n,pi:longint;

procedure print;
begin
writeln(f2,-1);
close(f2);
halt;
end;

procedure print0;
begin
writeln(f2,0);
close(f2);
halt;
end;


procedure init;
var
i,j,t1,t2,all:longint;
begin
assign(f1,fin);reset(f1);
assign(f2,fout);rewrite(f2);
readln(f1,n);
all:=0;
d[n+1]:=0;a[n+1]:=0;
for i:=n downto 1 do
begin
readln(f1,d[i],a[i]);
inc(all,a[i]);
end;
readln(f1,d[0],pi);
close(f1);
if all+pi<d[0] then print;
if pi>=d[0] then print0;

filldword(f,sizeof(f) div 4,maxlongint);
filldword(p,sizeof(p) div 4,maxlongint);
f[0,1]:=0;f[0,0]:=0;
p[0,1]:=pi;p[0,0]:=pi;

end;


procedure main;
var
i,k:longint;
begin
for i:=1 to n+1 do
begin
for k:=i-1 downto 0 do
 begin

  if p[k,0]>=d[k]-d[i] then
   if f[k,0]<f[i,0] then   {上一次不加油}
    begin
      f[i,0]:=f[k,0];
      p[i,0]:=p[k,0]-(d[k]-d[i]);
    end;
  if p[k,1]>=d[k]-d[i] then
    if f[k,1]<f[i,0] then  {上一次加油}
     begin
      f[i,0]:=f[k,1];
      p[i,0]:=p[k,1]-(d[k]-d[i]);
    end;
  {此次不加油}

  if p[k,0]>=d[k]-d[i] then  {上一次不加油}
  if f[k,0]<>maxlongint then
   if f[k,0]+1<f[i,1] then
    begin
      f[i,1]:=f[k,0]+1;
      p[i,1]:=p[k,0]-(d[k]-d[i])+a[i];
    end;
  if p[k,1]>=d[k]-d[i] then {上一次加油}
   if f[k,1]<>maxlongint then
    if f[k,1]+1<f[i,1] then
     begin
      f[i,1]:=f[k,1]+1;
      p[i,1]:=p[k,1]-(d[k]-d[i])+a[i];
    end;
  {此次加油}



 end;
 if (f[i,1]=maxlongint) and (f[i,0]=maxlongint) then print;
end;

writeln(f2,f[n+1,0]);
close(f2);
end;

begin
init;
main;
end.