//Top down approach
#include<bits/stdc++.h>
using namespace std;
 
#define MAX_N 2010
 
int  n, val[MAX_N], wt[MAX_N], memo[MAX_N][MAX_N];
 
 
int knapSack(int n, int w)
{
   if (memo[n][w] != -1)       return memo[n][w];
   // Base Case
   if (n == 0 || w == 0)  return 0;
 
 
   else if (wt[n-1] > w)  return memo[n][w] = knapSack(n-1,w);
 
   else return memo[n][w] = max(val[n-1] + knapSack(n-1, w-wt[n-1]), knapSack(n-1, w));
}
 
 
 
 
int main()
{
         int n, mw;
         memset(memo, -1, sizeof memo);
 
         cin>>mw>>n;
 
         for(int i=0;i<n;i++)   cin>>wt[i]>>val[i];
 
         cout<<knapSack(n,mw)<<endl;
 
         return 0;
}
 
 

Ly9Ub3AgZG93biBhcHByb2FjaAojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBNQVhfTiAyMDEwCgppbnQgIG4sIHZhbFtNQVhfTl0sIHd0W01BWF9OXSwgbWVtb1tNQVhfTl1bTUFYX05dOwoKCmludCBrbmFwU2FjayhpbnQgbiwgaW50IHcpCnsKICAgaWYgKG1lbW9bbl1bd10gIT0gLTEpICAgICAgIHJldHVybiBtZW1vW25dW3ddOwogICAvLyBCYXNlIENhc2UKICAgaWYgKG4gPT0gMCB8fCB3ID09IDApICByZXR1cm4gMDsKCgogICBlbHNlIGlmICh3dFtuLTFdID4gdykgIHJldHVybiBtZW1vW25dW3ddID0ga25hcFNhY2sobi0xLHcpOwoKICAgZWxzZSByZXR1cm4gbWVtb1tuXVt3XSA9IG1heCh2YWxbbi0xXSArIGtuYXBTYWNrKG4tMSwgdy13dFtuLTFdKSwga25hcFNhY2sobi0xLCB3KSk7Cn0KCgoKCmludCBtYWluKCkKewogICAgICAgICBpbnQgbiwgbXc7CiAgICAgICAgIG1lbXNldChtZW1vLCAtMSwgc2l6ZW9mIG1lbW8pOwoKICAgICAgICAgY2luPj5tdz4+bjsKCiAgICAgICAgIGZvcihpbnQgaT0wO2k8bjtpKyspICAgY2luPj53dFtpXT4+dmFsW2ldOwoKICAgICAgICAgY291dDw8a25hcFNhY2sobixtdyk8PGVuZGw7CgogICAgICAgICByZXR1cm4gMDsKfQoK