using namespace std;
int w[111]={};	 
int v[111]={}; 	
int bagV,m;				 
int dp[111][111]={{0}};	
int item[111]; 		
void findMax()
{
	for(int i=1;i<=m;i++)
	{
		for(int j=1;j<=bagV;j++)
		{
			if(j<w[i])
			{
				dp[i][j]=dp[i-1][j];
			}
			else
			{
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
			}
		}
	}
}
void findWhat(int i,int j)		//最优解情况 
{
	if(i>=0)
	{
		if(dp[i][j]==dp[i-1][j])
		{
			item[i]=0;
			findWhat(i-1,j);
		}
		else if(j-w[i]>=0&&dp[i][j]==dp[i-1][j-w[i]]+v[i])
		{
			item[i]=1;
			findWhat(i-1,j-w[i]);
		}
	}
}
void print()
{
	cout<<dp[m][bagV];
}
int main()
{
	cin>>bagV>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>w[i]>>v[i];
	 } 
	findMax();
	findWhat(m,bagV);
	print();
	return 0;
}```