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