#include <bits/stdc++.h>
using namespace std;
int dp[10003];
int main(){
	int h,n;cin>>h>>n;
	for (int j=0;j<10003;j++) dp[j]=1e9;
	dp[0]=0;
	for (int i=1;i<=n;i++){
		int a,b;cin>>a>>b;
		for (int j=0;j<=h;j++)
			dp[min(h,j+a)]=min(dp[min(h,j+a)],dp[j]+b);
	}
	cout<<dp[h];
}