#include <stdio.h>

int m,n,l1[1000001],d[1000001],rez,comp=0;

int partition( int a[], int l, int r) {
   int pivot, i, j, t;
   pivot = a[l];
   i = l; j = r+1;
		
   while( 1)
   {
   	do ++i; while( a[i] <= pivot && i <= r );
   	do --j; while( a[j] > pivot );
   	if( i >= j ) break;
   	t = a[i]; a[i] = a[j]; a[j] = t;
        t = l1[i]; l1[i] = l1[j]; l1[j] = t;
   }
   t = a[l]; a[l] = a[j]; a[j] = t;
   return j;
}

void quickSort( int a[], int l, int r)
{
   int j;

   if( l < r ) 
   {
   
        j = partition( a, l, r);
       quickSort( a, l, j-1);
       quickSort( a, j+1, r);
   }
	
}

void citire() {
  freopen("orase.in","r",stdin);
   freopen("orase.out","w",stdout);
     int i;
     scanf("%d",&m);
     scanf("%d",&n);
     for (i=0; i<n; ++i) {
         scanf("%d",&d[i]);
         scanf("%d",&l1[i]);
      }
}  

void rezolvare() {
     int k;
     int i,j;
     quickSort(d,0,n-1);
	for (i=0; i< n; ++i)
           printf("%d ",d[i]);
              for (  i = 1; i < n; ++i )
    {
        if ( l1[i] + l1[comp] + (d[i] - d[comp]) > rez )
            rez = l1[i] + l1[comp] + (d[i]- d[comp]);

        if ( l1[comp] + (m - d[comp]) < l1[i] + (m - d[i]) )
            comp = i;
    }
             
               
}   
              
int main() {
int i;
    freopen("orase.out","w",stdout);
    citire();
    rezolvare();
    printf("%d",rez);
    return 0;
}