#include<iostream> #include<algorithm> using namespace std; int n,m,f[1005],i,v,w,j; int main() { cin>>m>>n; for(i=1;i<=n;i++){ cin>>v>>w; for(j=m;j>=v;j--)f[j]=max(f[j],f[j-v]+w); } cout<<f[m]<<endl; return 0; }