#include<bits/stdc++.h> using namespace std; int a,b,c,d[10035],e[10004],f,g,h[10001]; int main() { cin>>a>>b; for(c=1;c<=b;c++) { cin>>d[c]>>e[c]; for(f=a;f>=d[c];f--) h[f]=max(h[f],h[f-d[c]]+e[c]); } cout<<h[a]; return 0; }