#include<bits/stdc++.h> using namespace std; int f[700010],n,m,c[510],w[510]; int main() { scanf("%d%d",&m,&n); for (int i=1;i<=n;++i) scanf("%d%d",&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]); printf("%d\n",f[m]); return 0; }