Pagini recente » Cod sursa (job #281919) | Cod sursa (job #1788497) | Cod sursa (job #2893316) | Cod sursa (job #867057) | Cod sursa (job #69734)
Cod sursa(job #69734)
#include <stdio.h>
#include <algorithm>
#define Nmax 50000
using namespace std;
int N,M,d[Nmax],l[Nmax],x[Nmax],i;
long long a[Nmax],maxim;
bool cmp(int a,int b)
{
return (d[x[a]]<d[x[b]]);
}
int main()
{
freopen("orase.in","r",stdin);
scanf("%d %d",&M,&N);
for (i=0;i<N;++i)
{
scanf("%d %d",&d[i],&l[i]);
x[i]=i;
}
fclose(stdin);
sort(x,x+N,cmp);
a[0]=l[x[0]];
for (i=1;i<N-1;++i)
{
if (a[i-1]+d[x[i]]-d[x[i-1]]>l[x[i]]) a[i]=a[i-1]+d[x[i]]-d[x[i-1]];
else a[i]=l[x[i]];
}
maxim=l[x[N-1]]+a[N-2]+d[x[N-1]]-d[x[N-2]];
for (i=N-2;i>1;--i)
if (l[x[i]]+a[i-1]+d[x[i]]-d[x[i-1]]>maxim) maxim=l[x[i]]+a[i-1]+d[x[i]]-d[x[i-1]];
freopen("orase.out","w",stdout);
printf("%lld",maxim);
fclose(stdout);
return 0;
}