#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

struct node
{
    int a;
    int b;
}v[110];

int min(int a,int b)
{
    return a<b?a:b;
}

int cmp(node a,node b)
{
    return a.b<b.b;
}

int main()
{
    int dp[110];
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        int i,j;
        int ans=0;
        for(i=0;i<m;i++)
        {
            scanf("%d %d",&v[i].a,&v[i].b);
            int w;
            w=n/v[i].a;
            if(n%v[i].a) w++;
            if(!ans) ans=v[i].b*w;
            else ans=min(ans,v[i].b*w);
        }
        printf("%d\n",ans);
    }
    return 0;
}