记录编号	15441	评测结果	AAAAAAAAAA
题目名称	[USACO Mar07] 平衡的阵容	最终得分	100
用户昵称	EnAsn	是否通过	通过
代码语言	Pascal	运行时间	0.179 s
提交时间	2009-11-13 08:37:20	内存使用	0.68 MiB

program ex;
type
 ss=array[1..50000,1..2]of longint;
 sz=array[0..50000]of longint;
var
 f:ss;
 hx:sz;
 n:longint;
procedure init;
 var
  i:longint;
 begin
  assign(input,'balance.in');
  assign(output,'balance.out');
  reset(input);
  rewrite(output);
  readln(n);
  for i:=1 to n do
   begin
    readln(f[i,1],f[i,2]);
    if f[i,1]=0 then f[i,1]:=-1;
   end;
  close(input);
 end;
procedure qsort(l,r:longint);
 var
  i,j,x,y:longint;
 begin
  i:=l;j:=r;x:=f[(l+r)div 2,2];
  repeat
   while f[i,2]<x do inc(i);
   while x<f[j,2] do dec(j);
   if i<=j then
    begin
     y:=f[i,2];f[i,2]:=f[j,2];f[j,2]:=y;
     y:=f[i,1];f[i,1]:=f[j,1];f[j,1]:=y;
     inc(i);dec(j);
    end;
 until i>j;
 if l<j then qsort(l,j);
 if i<r then qsort(i,r);
 end;
procedure main;
 var
  i,j:longint;
  tot,max:longint;
 begin
  tot:=0;
  max:=0;
  for i:=1 to n do
   begin
    tot:=tot+f[i,1];
    if (hx[tot]>i)or(hx[tot]=0) then hx[tot]:=i;
   end;
  tot:=0;
  for i:=1 to n do
   begin
    tot:=tot+f[i,1];
    if hx[tot]+1<=n then
    if f[i,2]-f[hx[tot]+1,2]>max then max:=f[i,2]-f[hx[tot]+1,2];
   end;
  writeln(max);
  close(output);
 end;
begin
 init;
 qsort(1,n);
 main;
end.