#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int main()
{
int p[1001],w[101];
int t,m,f[1001][101];
memset(f,0,sizeof(f));
memset(w,0,sizeof(w));
memset(p,0,sizeof(p));
cin>>t>>m;
for(int i=1;i<=m;i++)
{
cin>>w[i]>>p[i];
}
for(int i=1;i<=m;i++)
{
for(int j=0;j<=t;j++)
{
f[i][j]=f[i-1][j];
if((j>=w[i])&&((f[i-1][j-w[i]]+p[i])>f[i][j]))
{
f[i][j]=f[i-1][j-w[i]]+p[i];
}
}
}
cout<<f[m][t]<<endl;
return 0;
}