记录编号	137	评测结果	AAAAAAAAAA
题目名称	[POI 1997] 阶梯教室设备利用	最终得分	100
用户昵称	thegy	是否通过	通过
代码语言	Pascal	运行时间	0.058 s
提交时间	2008-04-25 20:43:50	内存使用	0.30 MiB

program rez;
var
  fin,fout:text;
  n,i,p,te:longint;
  be,en:array[1..10001]of longint;
  f:array[0..30001]of longint;
procedure qsort(l, r: Integer);
var
  i, j, x, y: integer;
begin
  i := l; j := r; x := en[(l+r) DIV 2];
  repeat
    while en[i] < x do i := i + 1;
    while x < en[j] do j := j - 1;
    if i <= j then
    begin
      y := en[i]; en[i] := en[j]; en[j] := y;
      y := be[i]; be[i] := be[j]; be[j] := y;
      i := i + 1; j := j - 1;
    end;
  until i > j;
  if l < j then qsort(l, j);
  if i < r then qsort(i, r);
end;
function max(x,y:longint):longint;
begin
  if x>y then max:=x
  else max:=y;
end;
begin
  assign(fin,'rez.in'); reset(fin);
  assign(fout,'rez.out'); rewrite(fout);
  read(fin,n);
  for i:=1 to n do
    read(fin,be[i],en[i]);
  qsort(1,n);
  te:=en[n];
  en[n+1]:=en[n]-1;
  p:=1;
  f[0]:=0;
  for i:=1 to te do
  begin
    if i=en[p] then
    begin
      f[i]:=max(f[i-1],f[be[p]]+en[p]-be[p]);
      while en[p]=en[p+1] do
      begin
        inc(p);
        f[i]:=max(f[i],f[be[p]]+en[p]-be[p]);
      end;
      inc(p);
    end
    else
    begin
      f[i]:=f[i-1];
    end;
  end;
  writeln(fout,f[te]);
  close(fout);
end.