#include<iostream>
#include<cstring>
#include<cstdio>

int n,m,x,y,min;

int main()
{
    int i,j,s;
    while (scanf("%d%d",&n,&m) != EOF)
    {
        min = 1 << 30;
        for (i = 1; i <= m; i++)
        {
            scanf("%d%d",&x,&y);
            if (n % x == 0) s = n/x*y;else s = (n/x+1)*y;
            if (min > s) min = s;
        }
        printf("%d\n",min);
    }
    return 0;
}