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