#include "iostream"
#include "string.h"
using namespace std;
#define size 10005
int f[size];
int main()
{
    int t, l, i, v, s, t1;
    cin>>t>>l;
    memset(f, 0, sizeof(f));
    for(i=0; i<l; i++)
    {
        cin>>s>>t1;
        for(v=t1; v<=t; v++) //這里一定是v=t1，要不然，v-t1就會出現(xiàn)小于0的情況，很明顯就會出錯了。
            f[v] = max(f[v], f[v-t1]+s);
    }
    cout<<f[t]<<endl;
}