#include <fstream>
using namespace std;
ifstream cin("medic.in");
ofstream cout("medic.out");
int mn[1001][1001],w[101],v[101];
int f(int i,int j)
{
	if(j==0||i==0)
	{
		mn[i][j]=0;
		return 0;
	}
	if(j<w[i])
	{
		mn[i][j]=mn[i-1][j];
	    return 0;
	}
	if(j>=w[i])
		mn[i][j]=max(v[i]+mn[i-1][j-w[i]],mn[i-1][j]);
		return 0;
}
int main()
{
	int t,m,i,j;
	cin>>t>>m;
	for(i=1;i<=m;i++)
		cin>>w[i]>>v[i];
	for(i=0;i<=m;i++)
		for(j=0;j<=t;j++)
			f(i,j);
		cout<<mn[m][t]<<endl;
	return 0;
	cin.close();cout.close();
}