#include<bits/stdc++.h> using namespace std; int m,n,w[500],v[500],f[500][500]; int main() { cin>>m>>n; for(int a=1;a<=n;a++) cin>>w[a]>>v[a]; for(int a=1;a<=n;a++) { for(int b=m;b>=1;b--) { if(b>=w[a]) f[a][b]=max(f[a][b],f[a][b-w[a]]+v[a]); f[a+1][b]=f[a][b]; } } cout<<f[n][m]; return 0; }