#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
long long res[1010];
long long a,b;
int dp(long long x,long long y,long long z)
{
	long long total = y;
	for(int i = 1;i <= z;++i)
	{
		y *= total;
	}
	return x*y;
}
int main()
{
	long long n,m;
	scanf("%lld%lld",&n,&m); 
	memset(res,0x7f7f,sizeof(res));
    res[0] = 0;
	for(int i = 1;i <= m; i++)
	{
		scanf("%lld%lld",&a,&b);
		for(int j = n;j >= 1; j--)
		{
			for(int k = 1;k <= j; k++)
			{
				res[j] = min(res[j],res[j-k] + (long long)dp(a,k,b));
			}
		}
	}
	printf("%lld",res[n]);
	return 0;
}

淦谢；