#include  < iostream >

using   namespace  std;

#define  N 100001

int  nk[ 11 ], dk[ 11 ], n, m, ans[N], num[N];

int  main(){
     while ( scanf( " %d%d " , & m, & n ) !=  EOF ){
         for (  int  i =   0 ; i <  n;  ++ i ) scanf( " %d%d " , nk +  i, dk +  i );
         for (  int  i =   0 ; i <=  m;  ++ i ) ans[i] =   0 ; ans[ 0 ] =   1 ;
        
         for (  int  i =   0 ; i <  n;  ++ i ){
             for (  int  j =   0 ; j <=  m;  ++ j ) num[j] =   0 ;
            
             for (  int  j =  dk[i]; j <=  m;  ++ j )
             if (  !  ans[j]  &&  ans[j - dk[i]]  &&  num[j -  dk[i]] <  nk[i] ){
                num[j] =  num[j - dk[i]] +   1 ;
                ans[j] =   1 ; }
        }
        
         int  res =  m;
         while ( ans[res] ==   0   &&  res >=   1  ) res -- ;
        printf( " %d\n " , res );
    }
    
     return   0 ;
}