#include<bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 5;
int main()
{
	int h, n;
	cin>>h>>n;
	
	vector<int> dp(h+1, INF);
	dp[0] = 0; 	
	while(n-- ) {
		int ap, cost;
		cin>>ap>>cost;
		
		for(int health=0; health<=h; health++)
		{
			int j = min(health + ap, h);
			
			dp[j] = min(dp[j], dp[health] + cost);
		}
	}
	cout<<dp[h];
	return 0;
}