#include<bits/stdc++.h>
using namespace std;
int dp[10050],a[1050],b[1050];
int main()
{
	memset(dp,0x7f,sizeof(dp));
	dp[0]=0;
	int h,n;
	cin>>h>>n;
	for (int i=1;i<=n;i++)
		cin>>a[i]>>b[i];
	for (int i=1;i<=n;i++)
		for (int j=a[i];j<=h+a[i];j++)
			dp[min(h,j)]=min(dp[min(h,j)],dp[j-a[i]]+b[i]);
	/*for (int i=0;i<=h;i++)
		cout<<dp[i]<<endl;*/
	cout<<dp[h];
	return 0;
}