#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
int h,n,a,b,c[11005];
int main(){
	scanf("%d%d", &h, &n);
	fill(c+1,c+h+1,(int)1e9);
	rep(i,n){
		scanf("%d%d", &a, &b);
		rep(j,h+1) c[j] = min(c[j],(j>a?c[j-a]:0)+b);
	}
	printf("%d\n", c[h]);
}