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