#include <bits/stdc++.h>
using namespace std;
int main(){
	int h, n;
	cin >> h >> n;
	vector<int> a(n), b(n);
	for(int i=0; i<n; ++i) cin >> a[i] >> b[i];

	int m=h+*max_element(a.begin(),a.end());
	vector<int> dp(m, 1e9);
	dp[0]=0;
	for(int i=1; i<m; ++i){
		for(int j=0; j<n; ++j){
			if(a[j]>i) continue;
			dp[i]=min(dp[i],b[j]+dp[i-a[j]]);
		}
	}

	cout << *min_element(dp.begin()+h,dp.end()) << endl;
}