| 比赛 | 
    20100913 | 
    评测结果 | 
    AWWWWWTTTW | 
    | 题目名称 | 
    越狱 | 
    最终得分 | 
    10 | 
    | 用户昵称 | 
    Achilles | 
    运行时间 | 
    0.000 s  | 
    | 代码语言 | 
    Pascal | 
    内存使用 | 
    0.00 MiB  | 
    | 提交时间 | 
    2010-09-13 21:28:26 | 
显示代码纯文本
program prisonbreak;
var
  sz:array[0..10050,1..2]of longint;
  oil,t,t2:array[0..10050]of longint;
  n,i,j,temp,temp2,min:longint;
procedure qsort(a,b:longint);
var
  p1,p2:longint;
begin
  p1:=a;
  p2:=b;
  if a<b then begin
    while p1<p2 do
    begin
      while (p1<p2)and(sz[p1,1]>sz[p2,1]) do
        p2:=p2-1;
      sz[0]:=sz[p1];
      sz[p1]:=sz[p2];
      sz[p2]:=sz[0];
      while (p1<p2)and(sz[p1,1]>sz[p2,1]) do
        p1:=p1+1;
      sz[0]:=sz[p1];
      sz[p1]:=sz[p2];
      sz[p2]:=sz[0];
    end;
    qsort(a,p1-1);
    qsort(p1+1,b);
  end;
end;
begin
  assign(input,'prisonbreak.in');
  assign(output,'prisonbreak.out');
  reset(input);
  rewrite(output);
  readln(n);
  n:=n+1;
  for i:=1 to n do
    readln(sz[i,1],sz[i,2]);
  qsort(1,n);
  n:=n+1;
  for i:=0 to n do
    oil[i]:=-2000000000;
  oil[0]:=sz[1,2];
  for i:=2 to n do
  begin
    temp:=sz[i-1,1]-sz[i,1];
    for j:=0 to n do
      if oil[j]>0 then begin
        if oil[j]>=temp then
        begin
          t[j]:=oil[j]-temp;
        end
        else t[j]:=-2000000000;
      end
      else t[j]:=-2000000000;
    temp2:=temp;
    temp:=temp-sz[i,2];
    t2[0]:=-2000000000;
    for j:=0 to n-1 do
      if oil[j]>0 then
      begin
        if temp2<=oil[j] then begin
          t2[j+1]:=oil[j]-temp;
        end
        else t2[j+1]:=2000000000;
      end
      else t2[j+1]:=-2000000000;
    for j:=0 to n do
      if t[j]>t2[j] then oil[j]:=t[j] else oil[j]:=t2[j];
  end;
  min:=0;
  for i:=0 to n do
    if oil[i]>=0 then begin
      writeln(i);
      min:=1;
      break;
    end;
  if min=0 then writeln(-1);
  close(input);
  close(output);
end.