program tyn;
type
  cow=record
    zz,zb:longint;
  end;
var
  cows:array[0..50000] of cow;
  n,i,max,zz0,zz1:longint;
procedure qsort(l,r:longint);
var
  x,y,mid,c:longint;
begin
  x:=l;
  y:=r;
  mid:=cows[(l+r) div 2].zb;
  repeat
    while cows[x].zb<mid do inc(x);
    while cows[y].zb>mid do dec(y);
    if x<=y then
    begin
      cows[0].zz:=cows[x].zz;
      cows[x].zz:=cows[y].zz;
      cows[y].zz:=cows[0].zz;
      cows[0].zb:=cows[x].zb;
      cows[x].zb:=cows[y].zb;
      cows[y].zb:=cows[0].zb;
      inc(x);
      dec(y);
    end;
  until x>y;
  if l<y then qsort(l,y);
  if r>x then qsort(x,r);
end;
begin
  assign(input,'balance.in');
  reset(input);
  assign(output,'balance.out');
  rewrite(output);
  readln(n);
  zz1:=0;
  for i:=1 to n do
    readln(cows[i].zz,cows[i].zb);
  qsort(1,n);
  for i:=1 to n do
    zz1:=zz1+cows[i].zz;
  zz0:=n-zz1;
  max:=cows[n].zb-cows[1].zb;
  i:=1;
  repeat
    if zz0=zz1 then break;
    if zz1>zz0 then
    begin
      if (cows[i].zz=1) and (cows[n].zz=0) then
      begin
        i:=i+1;
        max:=cows[n].zb-cows[i].zb;
        zz1:=zz1-1;
      end else
        if (cows[i].zz=0) and (cows[n].zz=1) then
        begin
          n:=n-1;
          max:=cows[n].zb-cows[i].zb;
          zz1:=zz1-1;
        end else
          if (cows[i+1].zb-cows[i].zb)>(cows[n].zb-cows[n-1].zb) then
          begin
            if cows[n].zz=1 then zz1:=zz1-1 else zz0:=zz0-1;
            n:=n-1;
            max:=cows[n].zb-cows[i].zb;
          end else
          begin
            if cows[i].zz=1 then zz1:=zz1-1 else zz0:=zz0-1;
            i:=i+1;
            max:=cows[n].zb-cows[i].zb;
          end;
    end else
    begin
      if (cows[i].zz=0) and (cows[n].zz=1) then
      begin
        i:=i+1;
        max:=cows[n].zb-cows[i].zb;
        zz0:=zz0-1;
      end else
        if (cows[i].zz=1) and (cows[n].zz=0) then
        begin
          n:=n-1;
          max:=cows[n].zb-cows[i].zb;
          zz0:=zz0-1;
        end else
          if (cows[i+1].zb-cows[i].zb)>(cows[n].zb-cows[n-1].zb) then
          begin
            if cows[n].zz=1 then zz1:=zz1-1 else zz0:=zz0-1;
            n:=n-1;
            max:=cows[n].zb-cows[i].zb;
          end else
          begin
            if cows[i].zz=1 then zz1:=zz1-1 else zz0:=zz0-1;
            i:=i+1;
            max:=cows[n].zb-cows[i].zb;
          end;
    end;
  until zz0=zz1;
  writeln(max);
  close(input);
  close(output);
end.