Pagini recente » Cod sursa (job #491951) | Cod sursa (job #2248210) | Cod sursa (job #3165543) | Cod sursa (job #2968732) | Cod sursa (job #67912)
Cod sursa(job #67912)
#include<stdio.h>
#include<stdlib.h>
#define Nm 50001
#define max(a,b) ((a)>(b)?(a):(b))
int D[Nm],L[Nm],n,m,sol;
void read()
{
int i;
freopen("orase.in","r",stdin);
scanf("%d%d",&m,&n);
for(i=0;i<n;++i)
scanf("%d%d",D+i,L+i);
}
int cmp(const void *x, const void *y)
{
return D[*(int*)x]-D[*(int*)y];
}
void solve()
{
int P[Nm],M[Nm],i;
for(i=0;i<n;++i)
P[i]=i;
qsort(P,n,sizeof(int),cmp);
M[n-1]=D[P[n-1]]+L[P[n-1]];
for(i=n-2;i>0;--i)
M[i]=max(M[i+1],D[P[i]]+L[P[i]]);
sol=0;
for(i=0;i<n-1;++i)
sol=max(sol,M[i+1]-D[P[i]]+L[P[i]]);
}
void write()
{
freopen("orase.out","w",stdout);
printf("%d\n",sol);
}
int main()
{
read();
solve();
write();
return 0;
}