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