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