#include<bits/stdc++.h> using namespace std; int n,m,w[31],c[31],f[2001]; 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 v=m;v>=w[i];v--){ f[v]=max(f[v-w[i]]+c[i],f[v]); } } cout<<f[m]; }