/*
ID:zhjshar1
PROG:inflate
LANG:C++
*/
#include <fstream>
using namespace std;

ifstream  in( "inflate.in" );
ofstream out( "inflate.out" );

int main(){
    const int MAXN = 10010;
    int money, totobj, f[MAXN]={0}, value, price, i, j, tem;
    in >>money >>totobj;
    for( i=0; i<totobj; ++i ){
         in >>value >>price;
         for( j=price; j<=money; ++j )
              if( (tem=f[j-price]+value) > f[j] ) f[j] = tem;
    }
    out <<f[money] <<endl;
    return 0;
}