#include<stdio.h>
#define maxg 1005
#define maxw 10000005
int w,g,i,j;
long x,y;
long long a[maxw],min,poz,poz1;
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,&y);
for(j=1;j<=poz1;j++)
if(a[j])
{if(a[j+x]==0||a[j+x]>y+a[j])
a[j+x]=a[j]+y;
if(j+x>poz)
poz=j+x;
if(j+x>=w && a[j]+y<min)
min=a[j]+y;}
if(a[x]==0)
a[x]=y;
else if(a[x]>y)
a[x]=y;
if(x>=w && y<min)
min=y;
if(x>poz)
poz=x;
poz1=poz;}
if(min==maxw)
fprintf(d,"-1");
else
fprintf(d,"%lld",min);

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