#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int,int>;

int main(){
	int h, n;
	cin >> h >> n;
	vector<int> ar(h, 1000000000);
	rep(i, n){
		int a, b;
		cin >> a >> b;
		rep(j, h){
			ar.at(j) = min(ar.at(j), (j/a+1)*b);
			if(j >= a) ar.at(j) = min(ar.at(j), ar.at(j-a) + b);
		}
	}
	cout << ar.at(h-1) << endl;
	return 0;
}