#include<bits/stdc++.h> using namespace std; int f[700010],n,m,c[510],w[510]; int main() { cin>>m>>n; for(int i=1;i<=n;++i) { cin>>c[i]>>w[i]; } for(int i=0;i<=m;++i) { f[i]=0; } for(int i=1;i<=n;++i) { for(int j=m;j>=c[i];--j) { f[j]=max(f[j],f[j-c[i]]+w[i]); } } cout<<f[m]; return 0; }