//Top down approach
#include<bits/stdc++.h>
using namespace std;
#define MAX_N 2001
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;
}
Ly9Ub3AgZG93biBhcHByb2FjaAojaW5jbHVkZTxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwogCiNkZWZpbmUgTUFYX04gMjAwMQogCmludCAgbiwgdmFsW01BWF9OXSwgd3RbTUFYX05dLCBtZW1vW01BWF9OXVtNQVhfTl07CiAKIAppbnQga25hcFNhY2soaW50IG4sIGludCB3KQp7CiAgIGlmIChtZW1vW25dW3ddICE9IC0xKSAgICAgICByZXR1cm4gbWVtb1tuXVt3XTsKICAgLy8gQmFzZSBDYXNlCiAgIGlmIChuID09IDAgfHwgdyA9PSAwKSAgcmV0dXJuIDA7CiAKIAogICBlbHNlIGlmICh3dFtuLTFdID4gdykgIHJldHVybiBtZW1vW25dW3ddID0ga25hcFNhY2sobi0xLHcpOwogCiAgIGVsc2UgcmV0dXJuIG1lbW9bbl1bd10gPSBtYXgodmFsW24tMV0gKyBrbmFwU2FjayhuLTEsIHctd3Rbbi0xXSksIGtuYXBTYWNrKG4tMSwgdykpOwp9CiAKIAogCiAKaW50IG1haW4oKQp7CiAgICAgICAgIGludCBuLCBtdzsKICAgICAgICAgbWVtc2V0KG1lbW8sIC0xLCBzaXplb2YgbWVtbyk7CiAKICAgICAgICAgY2luPj5tdz4+bjsKIAogICAgICAgICBmb3IoaW50IGk9MDtpPG47aSsrKSAgIGNpbj4+d3RbaV0+PnZhbFtpXTsKIAogICAgICAgICBjb3V0PDxrbmFwU2FjayhuLG13KTw8ZW5kbDsKIAogICAgICAgICByZXR1cm4gMDsKfQ==