#include<iostream> using namespace std; const int N =1e6+10; int f[N]; int main() { int t,m, w, c; cin>>t>>m; for(int i=1;i<=m;i++) { cin >> w >> c; for (int j = t; j >= w; --j) f[j] = max(f[j], f[j - w] + c); } cout<<f[t] << endl; return 0; }