记录编号	8449	评测结果	AATTTTTTTA
题目名称	越狱	最终得分	50
用户昵称	francis	是否通过	未通过
代码语言	Pascal	运行时间	7.051 s
提交时间	2008-11-14 16:16:50	内存使用	4.05 MiB

program prisonbreak;
const
fin='prisonbreak.in';
fou='prisonbreak.out';
var
f:array[0..1005,0..1005]of longint;
a,b:array[0..10005]of longint;
k,min,i,j,n:longint;
f1,f2:text;

procedure sort(i,j:longint);
var
t1,t2,temp,k:longint;
begin
t1:=i; t2:=j;
k:=a[random(j-i+1)+i];
repeat
 while a[t1]>k do inc(t1);
 while a[t2]<k do dec(t2);
 if t1<=t2 then begin
 temp:=a[t1]; a[t1]:=a[t2]; a[t2]:=temp;
 temp:=b[t1]; b[t1]:=b[t2]; b[t2]:=temp;
 inc(t1); dec(t2);
 end;
until t1>=t2;
if t1<j then sort(t1,j);
if t2>i then sort(i,t2);
end;

procedure init;
begin
assign(f1,fin);
assign(f2,fou);
reset(f1); rewrite(f2);
read(f1,n);
for i:=n downto 0 do
read(f1,a[i],b[i]);
if n>=1000 then begin write(f2,-1); close(f1); close(f2); end;
sort(1,n);
inc(n);
for i:=0 to n do
for j:=0 to n do
f[i,j]:=-1;
f[0,0]:=b[0];
end;

procedure main;
begin
for  i:=1 to n do
for  j:=1 to i do
for  k:=0 to i-1 do
if f[k,j-1]>=(a[k]-a[i]) then
 begin
   if f[i,j]<f[k,j-1]+b[i]-(a[k]-a[i]) then
      f[i,j]:=f[k,j-1]+b[i]-(a[k]-a[i]);
 end;
end;

procedure print;
begin
for i:=1 to n do
if f[n,i]>=0 then begin min:=i; break; end;
dec(min);
write(f2,min);
close(f1); close(f2);
end;

begin
init;
main;
print;
end.