#include using namespace std; int f[10001],c[10001],w[10001],n,t; int main() { scanf("%d %d",&n,&t); for(int i=1;i<=t;i++) scanf("%d %d",&w[i],&c[i]); for(int i=1;i<=t;i++) for(int j=n;j>=w[i];j--) if(f[j]<f[j-w[i]]+c[i]) f[j]=f[j-w[i]]+c[i]; printf("%d",f[n]); return 0; }