#include <iostream>
#include <string.h>
using namespace std;
int dp[1005], w[105],v[105],T,M;
int max(int x,int y)
{    return x>y?x:y;   }
void  f( )
{   int i,j;
    for (i=1; i<=M; i++)
        for (j=T;j>=w[i]; j--)
          dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
int main()
{   int i;   
    cin>>T>>M;
    for ( i=1; i<=M; i++)  cin>>w[i]>>v[i];
    memset(dp,0,sizeof(dp));
    f( );   
    cout<<dp[T]<<endl;
}