#include <bits/stdc++.h>
using namespace std;
int w[105],v[105];
int f[1005]; 
int main()
{
	int t,n;
	cin>>t>>n;
	for(int i=0;i<n;i++)
	{
		cin>>w[i]>>v[i];
	}
	for(int i=0;i<n;i++)
	{
		for(int j=t;j>=w[i];j--)
		{
			f[i]=max(f[j],f[j-w[i]]+v[i]);
		}
	}
	cout<<f[t]<<endl;
	return 0;
}