#include <bits/stdc++.h>

using namespace std;

int main() {

int H,n;
cin>>H>>n;
vector<long long >a(n+10);
vector<long long >b(n+10);
vector<long long >dp(H+10,INT_MAX);

	for(int i = 0; i < n; ++i){
		cin >> a[i] >> b[i];
	}
	dp[0] = 0;
	for(int hlth = 0; hlth <= H; ++hlth){
		for(int i = 0; i < n; ++i){
			dp[hlth] = min(dp[max(0LL, hlth - a[i])] + b[i], dp[hlth] );
		}
	}
	cout << dp[H] << '\n';

return 0;
}