#include <iostream>
#include <algorithm>
using namespace std;
const int N(1004);
int f[N]={0};
int main()
{
	int t,m;
	cin>>t>>m;
	int w,v;
	for(int i=1;i<=m;i++)
	{
		cin>>w>>v;
		for(int j=t;j>=w;j--)
			f[j]=max(f[j],f[j-w]+v);
	}
	cout<<f[t]<<endl;
	return 0;
}
/**************************************************************
	Problem: 2254
	User: admin
	Language: C++
	Result: Accepted
	Time:46 ms
	Memory:2076 kb
****************************************************************/