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