#include<bits/stdc++.h> using namespace std; const int maxm = 1010 , maxn = 505; int m,n; int w[maxn], c[maxn]; int f[maxm]; int main() { cin>>m>>n; for(int i=1;i<=n;i++) cin>>w[i]>>c[i]; for(int i=1;i<=n;i++){ for(int j=m;j>=w[i];j--){ if(f[j - w[i]] + c[i] > f[j]) f[j] = f[j - w[i]] + c[i]; } } cout<<f[m]<<endl; return 0; }