#include<iostream> using namespace std; int a,b,c,d[1035],e[1004],f,g,h[10005][10005]; int main() { cin>>a>>b; for(c=1;c<=b;c++) cin>>d[c]>>e[c]; for(f=1;f<=b;f++) for(g=1;g<=a;g++) if(g>d[f]) h[f][g]=max(h[f-1][g-d[f]]+e[f],h[f-1][g]); else h[f][g]=h[f-1][g]; cout<<h[b][a]; return 0; }