//Top down approach
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 5
int n, val[MAX_N], wt[MAX_N], memo[MAX_N][MAX_N];
int knapSack(int n, int w)
{
if (memo[n-1][w-1] != -1) return memo[n-1][w-1];
// Base Case
if (n == 0 || w == 0) return 0;
else if (wt[n-1] > w) return memo[n-1][w-1] = knapSack(n-1,w);
else return memo[n-1][w-1] = 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;
}
Ly9Ub3AgZG93biBhcHByb2FjaAojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwogCiNkZWZpbmUgTUFYX04gNQogCmludCAgbiwgdmFsW01BWF9OXSwgd3RbTUFYX05dLCBtZW1vW01BWF9OXVtNQVhfTl07CiAKIAppbnQga25hcFNhY2soaW50IG4sIGludCB3KQp7CiAgIGlmIChtZW1vW24tMV1bdy0xXSAhPSAtMSkgICAgICAgcmV0dXJuIG1lbW9bbi0xXVt3LTFdOwogICAvLyBCYXNlIENhc2UKICAgaWYgKG4gPT0gMCB8fCB3ID09IDApICByZXR1cm4gMDsKIAogCiAgIGVsc2UgaWYgKHd0W24tMV0gPiB3KSAgcmV0dXJuIG1lbW9bbi0xXVt3LTFdID0ga25hcFNhY2sobi0xLHcpOwogCiAgIGVsc2UgcmV0dXJuIG1lbW9bbi0xXVt3LTFdID0gbWF4KHZhbFtuLTFdICsga25hcFNhY2sobi0xLCB3LXd0W24tMV0pLCBrbmFwU2FjayhuLTEsIHcpKTsKfQogCiAKIAogCmludCBtYWluKCkKewogICAgICAgICBpbnQgbiwgbXc7CiAgICAgICAgIG1lbXNldChtZW1vLCAtMSwgc2l6ZW9mIG1lbW8pOwogCiAgICAgICAgIGNpbj4+bXc+Pm47CiAKICAgICAgICAgZm9yKGludCBpPTA7aTxuO2krKykgICBjaW4+Pnd0W2ldPj52YWxbaV07CiAKICAgICAgICAgY291dDw8a25hcFNhY2sobixtdyk8PGVuZGw7CiAKICAgICAgICAgcmV0dXJuIDA7Cn0=