记录编号	15356	评测结果	AAAAAAAAAA
题目名称	[USACO Mar07] 平衡的阵容	最终得分	100
用户昵称	ybh	是否通过	通过
代码语言	Pascal	运行时间	0.191 s
提交时间	2009-11-12 14:28:14	内存使用	0.97 MiB

program PingHengDeZhenRong;
var
  a:array[0..50000] of longint;
  id:array[0..50000] of integer;
  sum:array[0..50000] of longint;
  hash:array[-50000..50000] of longint;
  n,i,max:longint;

procedure sort(l,r:longint);
var
  i,j,temp,x:longint;
begin
  i:=l;
  j:=r;
  x:=a[(l+r) div 2];
  repeat
    while a[i]<x do
      inc(i);
    while a[j]>x do
      dec(j);
    if i<=j then
    begin
      temp:=a[i];
      a[i]:=a[j];
      a[j]:=temp;
      temp:=id[i];
      id[i]:=id[j];
      id[j]:=temp;
      inc(i);
      dec(j)
    end
  until i>j;
  if i<r then sort(i,r);
  if l<j then sort(l,j)
end;

begin
  assign(input,'balance.in');
  reset(input);
  assign(output,'balance.out');
  rewrite(output);
  readln(n);
  fillchar(a,sizeof(a),0);
  fillchar(id,sizeof(id),0);
  fillchar(sum,sizeof(sum),0);
  for i:=0-n to n do
    hash[i]:=-1;
  for i:=1 to n do
  begin
    readln(id[i],a[i]);
    if id[i]=0
      then id[i]:=-1
  end;
  sort(1,n);
  hash[0]:=a[1];
  a[n+1]:=-1;
  for i:=1 to n do
  begin
    sum[i]:=sum[i-1]+id[i];
    if hash[sum[i]]=-1
      then hash[sum[i]]:=a[i+1]
  end;
  max:=0;
  for i:=1 to n do
  begin
    if (hash[sum[i]]>-1) and (a[i]-hash[sum[i]]>max)
      then max:=a[i]-hash[sum[i]];
  end;
  writeln(max);
  close(input);
  close(output)
end.