#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int NR=(1e3)+10,MR=(1e3)+10; int f[NR][MR],v[NR],w[NR]; int main() { int n,m,i,j; scanf("%d%d",&m,&n); for(i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]); //for(j=0;j<=m;j++) f[0][j]=0; for(i=1;i<=n;i++) for(j=1;j<=m;j++) { if(j-w[i]>=0) f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]); else f[i][j]=f[i-1][j]; } printf("%d",f[n][m]); return 0; }