#include<stdio.h>
int main()
{
    int n,m,i,j,a[100],b[100],sum,c;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        sum=0;
        for(i=0;i<m;i++)
        scanf("%d%d",&a[i],&b[i]);
        for(i=0;i<m;i++)
        {
            if(n%a[i]==0) c=n/a[i]*b[i];
            else c=(n/a[i]+1)*b[i];
            if(i==0) sum=c;
            else
            {
                if(c<sum) sum=c;
            }
        }
        printf("%d\n",sum);
    }
    return 0;
}