#include<stdio.h>
#define maxg 1005
#define maxw 10005
int w,g,i;
long x[maxg],y[maxg],j;
long long a[maxw],s,min;
FILE *f,*d;
int main()
{f=fopen("energii.in","r");
d=fopen("energii.out","w");
fscanf(f,"%d %d",&g,&w);
min=maxw;
for(i=1;i<=w;i++)
{fscanf(f,"%ld %ld",&x[i],&y[i]);
if(y[i]>s)
s=y[i];}
for(i=1;i<=s;i++)
a[i]=maxw;
for(i=1;i<=g;i++)
{if(y[i]<a[x[i]])
a[x[i]]=y[i];
for(j=x[i];j<=s;j++)
{if(a[j]>y[i]+a[j-x[i]]&&j%x[i])
a[j]=y[i]+a[j-x[i]];
if(j>=w && a[j]<min)
min=a[j];}}
if(min!=maxw)
fprintf(d,"%lld",min);
else fprintf(d,"-1");

fclose(f);
fclose(d);
return 0;}