const int N=200005;
const int M=605;
const int inf=-1e9;

int n,m;
int f[M];

struct node {
    int a,b;
    friend bool operator < (const node& a,const node& b) {
        return a.b*(b.a-b.b)>b.b*(a.a-a.b);
    }
} arr[N];

i32 main() {
    read(n),read(m);
    _rep(i,1,m) read(arr[i].a),read(arr[i].b);
    sort(arr+1,arr+1+m);
    int ans=0;
    if (n>300) {
        int a=arr[1].a,b=arr[1].b;
        int k=n-300;
        int cnt=k/(a-b);
        ans+=cnt*a;
        n-=cnt*(a-b);
    }
    // n ==> [300,600)
    _rep(i,1,m) _rrep(j,n-(arr[i].a-arr[i].b),arr[i].b) f[j]=max(f[j],f[j+(arr[i].a-arr[i].b)]+arr[i].a);
    // _rep(i,0,n) printf("f[%lld] = %lld\n",i,f[i]);
    int res=0;
    _rep(i,0,n) res=max(res,f[i]+i);
    ans+=res;
    write(ans);
    return 0;
}

WA*2，how？（已开 long long）