#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXH=1e4+5,MAXN=1005;
int h,n,a[MAXN],b[MAXN];
int f[MAXH];
int main(){
	scanf("%d%d",&h,&n);
	for(int i=1; i<=n; i++)
		scanf("%d%d",a+i,b+i);
	for(int i=1; i<=h; i++){
		f[i]=2e9;
		for(int j=1; j<=n; j++)
			f[i]=min(f[i],a[j]>i?b[j]:b[j]+f[i-a[j]]);
	}
	printf("%d\n",f[h]);
	return 0;
}