# include <stdio.h>

FILE *f,*h;

long n,q,w,S[101],g[101],v[101],s,i;

int main()
{

 f=fopen("pusculita.in","r");
 h=fopen("pusculita.out","w");

 fscanf(f,"%ld %ld",&s, &n);
 for (i=1;i<=n;i++)
	fscanf(f,"%ld %ld",&g[i], &v[i]);
 fclose(f);
 for (i=1;i<=s;i++)
	S[i]=2000000000;
 for (q=0;q<=s;q++)
  for (w=1;w<=n;w++)
	if (q>=g[w] && S[q]-S[q-g[w]]>v[w])
		S[q]=S[q-g[w]]+v[w];
 fprintf(h,"%ld", S[s]);
 fclose(h);
 return 0;
}