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