#include <stdio.h>
#define index(a,n,e) ((n)<0?(e):(a[n]))
#define updl(o,n) (o>(n)&&(o=(n)))
int main(){
	int h,n,dp[10010],a,m;
	scanf("%d%d",&h,&n);
	dp[0]=0;
	for(int i=1;i<=h;i++){
		dp[i]=2147483647;
	}
	for(int ii=0;ii<n;ii++){
		scanf("%d%d",&a,&m);
		for(int i=0;i<=h;i++){
			updl(dp[i],index(dp,i-a,0)+m);
		}
	}
	printf("%d\n",dp[h]);
	return 0;
}