#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1010;
int h,n,sum,w[N],c[N],f[N][10010];
int main(){
	cin>>h>>n;
	for(int i=1;i<=n;i++)
		scanf("%d%d",&w[i],&c[i]);
	for(int i=1;i<=h;i++)
		f[0][i]=199999999;
	for(int i=1;i<=n;i++)
		for(int j=0;j<=h;j++){
			f[i][j]=min(f[i-1][j],f[i][max(0,j-w[i])]+c[i]);
		}
	printf("%d\n",f[n][h]);
	return 0;
}