#include<bits/stdc++.h>
using namespace std ;
int w[3000];
int v[3000];
int dp[3000][3000];
int solve(int cap,int n)
{
      if(cap<0)return -9999999;
      else if(n<=0)return 0 ;
      else if (dp[cap][n]!=-1) return dp[cap][n] ;
      return dp[cap][n] = max(solve(cap-w[n],n-1)+v[n],max(0,solve(cap,n-1)));
}
int main()
{
  ios_base::sync_with_stdio(0);
  int cap,n;
  cin>>cap>>n;
  memset(dp,-1,sizeof(dp));
  for(int i=1;i<=n;i++)cin>>w[i]>>v[i];
  cout<<solve(cap,n)<<endl;
  return 0 ;
} 

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZCA7CmludCB3WzMwMDBdOwppbnQgdlszMDAwXTsKaW50IGRwWzMwMDBdWzMwMDBdOwppbnQgc29sdmUoaW50IGNhcCxpbnQgbikKewogICAgICBpZihjYXA8MClyZXR1cm4gLTk5OTk5OTk7CiAgICAgIGVsc2UgaWYobjw9MClyZXR1cm4gMCA7CiAgICAgIGVsc2UgaWYgKGRwW2NhcF1bbl0hPS0xKSByZXR1cm4gZHBbY2FwXVtuXSA7CiAgICAgIHJldHVybiBkcFtjYXBdW25dID0gbWF4KHNvbHZlKGNhcC13W25dLG4tMSkrdltuXSxtYXgoMCxzb2x2ZShjYXAsbi0xKSkpOwp9CmludCBtYWluKCkKewogIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7CiAgaW50IGNhcCxuOwogIGNpbj4+Y2FwPj5uOwogIG1lbXNldChkcCwtMSxzaXplb2YoZHApKTsKICBmb3IoaW50IGk9MTtpPD1uO2krKyljaW4+PndbaV0+PnZbaV07CiAgY291dDw8c29sdmUoY2FwLG4pPDxlbmRsOwogIHJldHVybiAwIDsKfSA=

NCA1CjEgOAoyIDQKMyAwCjIgNQoyIDM=

4 5
1 8
2 4
3 0
2 5
2 3