#include <iostream>
#include <math.h>
using namespace std;
int t,m,a[1005],b[1005];
int dp(int x[],int y[],int d,int sum,int i,int n){
	if (i<m)
	{
		
			if (x[i]>d)
			{
				return dp(x,y,d,sum,i+1,m);
			}
			else
			{
				return max(dp(x,y,d-x[i],sum+y[i],i+1,m),dp(x,y,d,sum,i+1,m));
				
				
			}
		
	}
	return sum;
}
int main() {
	cin>>t>>m;
	for (int i = 1;i <= m;i++)
	{
		cin>>a[i]>>b[i];
	}
	int ans=dp(a,b,t,0,1,m);
	cout<<ans;
    return 0;
}