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