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