#include<bits/stdc++.h>
using namespace std;

int dp[2005][2005],weight[20000],price[20000];
int main()
{
	long long int i,j,k,capacity,n;
	cin>>capacity;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>weight[i];
		cin>>price[i];
	}

    for(i=1;i<=n;i++)
    {
    	for(j=1;j<=capacity;j++)
    	{
    		if(j<weight[i])
    		{
    			dp[i][j]=dp[i-1][j];
    		}
    		else
    		{
    			dp[i][j]=max(dp[i-1][j-weight[i]]+price[i],dp[i-1][j]);
    		}
    	}
    }

    cout<<dp[n][capacity]<<endl;
  return 0;
}