Cod sursa(job #81338)
#include<stdio.h>
long a[50000],b[50000],d[50000],l[50000],m,n,i,j,q,max,p,k;
void interclasare(long st, long dr, long mij){
for(i=st;i<=dr;i++){
a[i]=d[i];
b[i]=l[i];
}
k=st-1;i=st;j=mij+1;
while(i<=mij && j<=dr)
if(a[i]<a[j]){
d[++k]=a[i];
l[k]=b[i++];
}
else{
d[++k]=a[j];
l[k]=b[j++];
}
for(q=i;q<=mij;q++){
d[++k]=a[q];
l[k]=b[q];
}
for(q=j;q<=dr;q++){
d[++k]=a[q];
l[k]=b[q];
}
}
void sort(long st, long dr){
long mij;
if(st<dr){
mij=(st+dr)/2;
sort(st,mij);
sort(mij+1,dr);
interclasare(st,dr,mij);
}
}
int main(){
freopen("orase.in","r",stdin);
freopen("orase.out","w",stdout);
scanf("%ld%ld",&m,&n);
for(i=0;i<n;i++)
scanf("%ld%ld",&d[i],&l[i]);
sort(0,n-1);
max=l[0];p=0;
for(i=1;i<n;i++){
max+=d[i]-d[i-1];
if(p<max+l[i])
p=max+l[i];
if(max<l[i])
max=l[i];
}
printf("%ld\n",p);
fclose(stdin);
fclose(stdout);
return 0;
}