#include <stdio.h>
#include <algorithm>
using namespace std;
FILE*f=fopen("rucsac.in","r");
FILE*g=fopen("rucsac.out","w");
int p[101][101],v[101],c[101],x,G,nr,i,n;
int main()
{
    fscanf(f,"%d",&G);
    fscanf(f,"%d",&nr);
    for(i=1;i<=nr;i++)
    {
        fscanf(f,"%d",&v[i]);
        fscanf(f,"%d",&c[i]);
    }
    for(i=1;i<=nr;i++)
    {
        for(x=1;x<v[i];x++)
            p[i][x]=p[i-1][x];
        for(x;x<=G;x++)
            p[i][x]=max(p[i-1][x],c[i]+p[i-1][x-v[i]]);
    }
    fprintf(g,"%d",p[nr][G]);
    return 0;
}