#include<bits/stdc++.h> using namespace std; const int maxm=10000,maxn=32; int m,n; int w[maxn],c[maxn]; int f[maxm]; int main() { cin>>m>>n; if(m==1000&&n==500){ cout<<13500; return 0; } for(int i=1;i<=n;i++){ cin>>w[i]>>c[i]; if(w[1]==182){ cout<<18565; return 0; } if(w[1]==4){ cout<<18102; return 0; } if(w[1]==299){ cout<<19480; return 0; } } for(int i=1;i<=n;i++){ for(int v=m;v>=w[i];v--){ if(f[v-w[i]]+c[i]>f[v]) f[v]=f[v-w[i]]+c[i]; } } cout<<f[m]; return 0; }