#include<bits/stdc++.h>
using namespace std;

const int maxn=1004,maxh=1e4+7;
int h,n,a[maxn],b[maxn];
long long f[maxh];

int main()
{
	scanf("%d %d",&h,&n);
	for(int i=1;i<=n;++i) {
		scanf("%d %d",&a[i],&b[i]);
	}
	memset(f,63,sizeof f);
	f[0]=0;
	for(int i=1;i<=n;++i) {
		for(int j=0;j<=h;++j) {
			if(j<a[i]) f[j]=min(f[j],1ll*b[i]);
			else f[j]=min(f[j],f[j-a[i]]+b[i]);
		}
	}
	printf("%lld",f[h]);
}