#include<bits/stdc++.h>//D using namespace std; const int N=110,M=1010; int a[N][M],w[N],v[N]; int main() { int n,m; cin>>n>>m; for(int i=1;i<=m;i++) cin>>w[i]>>v[i]; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) if(j>=w[i]) a[i][j]=max(a[i-1][j],a[i-1][j-w[i]]+v[i]); else a[i][j]=a[i-1][j]; cout<<a[m][n];
return 0; }