//Top down approach
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 2000
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;
}
Ly9Ub3AgZG93biBhcHByb2FjaAojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKI2RlZmluZSBNQVhfTiAyMDAwCgppbnQgIG4sIHZhbFtNQVhfTl0sIHd0W01BWF9OXSwgbWVtb1tNQVhfTl1bTUFYX05dOwoKCmludCBrbmFwU2FjayhpbnQgbiwgaW50IHcpCnsKICAgaWYgKG1lbW9bbl1bd10gIT0gLTEpICAgICAgIHJldHVybiBtZW1vW25dW3ddOwogICAvLyBCYXNlIENhc2UKICAgaWYgKG4gPT0gMCB8fCB3ID09IDApICByZXR1cm4gMDsKCgogICBlbHNlIGlmICh3dFtuLTFdID4gdykgIHJldHVybiBtZW1vW25dW3ddID0ga25hcFNhY2sobi0xLHcpOwoKICAgZWxzZSByZXR1cm4gbWVtb1tuXVt3XSA9IG1heCh2YWxbbi0xXSArIGtuYXBTYWNrKG4tMSwgdy13dFtuLTFdKSwga25hcFNhY2sobi0xLCB3KSk7Cn0KCgoKCmludCBtYWluKCkKewogICAgICAgICBpbnQgbiwgbXc7CiAgICAgICAgIG1lbXNldChtZW1vLCAtMSwgc2l6ZW9mIG1lbW8pOwoKICAgICAgICAgY2luPj5tdz4+bjsKCiAgICAgICAgIGZvcihpbnQgaT0wO2k8bjtpKyspICAgY2luPj53dFtpXT4+dmFsW2ldOwoKICAgICAgICAgY291dDw8a25hcFNhY2sobixtdyk8PGVuZGw7CgogICAgICAgICByZXR1cm4gMDsKfQoK