#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	int x[b+1][2]={};
	for(int i=1;i<=b;i++)
	{
		cin>>x[i][0]>>x[i][1];
	}
	int dp[b+1][a+1]={};
	for(int i=1;i<=b;i++)
	{
		for(int j=0;j<=a;j++)
		{
			dp[i][j]=dp[i-1][j];
			if(j>=x[i][0])
				dp[i][j]=max(dp[i-1][j],dp[i- 1][j- x[i][0]]+x[i][1]);
		}
	}
	cout <<dp[b-1][a-1];
	return 0;
}