Cod sursa(job #68603)

Utilizator CezarMocanCezar Mocan CezarMocan Data 28 iunie 2007 16:43:25
Problema Orase Scor 100
Compilator fpc Status done
Runda Arhiva de probleme Marime 1.05 kb
var n,m,i,j,max,nr1,nr2:longint;
    v,x,z:array[1..50010]of longint;

procedure qsort(ls,ld:longint);
var i,j,aux:longint;
begin
  i:=ls;j:=ld;
  while true do begin
    while (v[i]<=v[j])and(i<>j) do inc(i);
    if i=j then break;
    aux:=x[i];x[i]:=x[j];x[j]:=aux;
    aux:=v[i];v[i]:=v[j];v[j]:=aux;dec(j);
    while (v[i]<=v[j])and(i<>j) do dec(j);
    if i=j then break;
    aux:=x[i];x[i]:=x[j];x[j]:=aux;
    aux:=v[i];v[i]:=v[j];v[j]:=aux;inc(i);
  end;
  if j-1>ls then qsort(ls,j-1);
  if j+1<ld then qsort(j+1,ld);
end;

begin
assign(input,'orase.in');reset(input);
assign(output,'orase.out');rewrite(output);
readln(m,n);
for i:=1 to n do
        readln(v[i],x[i]);
qsort(1,n);
z[1]:=0;
z[2]:=v[2]-v[1]+x[1]+x[2];
for i:=3 to n do
        begin
        z[i]:=z[i-1]-x[i-1]+x[i]+(v[i]-v[i-1]);
        if v[i]-v[i-1]+x[i]+x[i-1]>z[i] then
                z[i]:=v[i]-v[i-1]+x[i]+x[i-1];
        end;
max:=0;
for i:=1 to n do
        if z[i]>max then
                max:=z[i];
writeln(max);
close(input);close(output);
end.