#include<bits/stdc++.h> using namespace std; const int N=1002; int w[N],c[N],f[N]; int main(){ int m,n; 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>=w[i];j--){ f[j]=max(f[j-w[i]]+c[i],f[j]); } } cout<<f[m]; }