#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int INF = 1001001001;

int main() {
	int h, n; cin >> h >> n;
	vector<int>dp(h + 1, INF);
	dp[0] = 0;
	for (int i = 0; i < n; i++) {
		int a, b; cin >> a >> b;
		for (int j = 0; j < h; j++) {
			int nj = min(j + a, h);
			dp[nj] = min(dp[nj], dp[j] + b);
		}
	}
	cout << dp[h] << endl;

	return 0;
}