#include <cstdio>
using namespace std;
const int INF=1e9;
const int WMAX=5001;
int d[WMAX];
int main()
{
	FILE *fin, *fout;
    int G,W,i,e,c,last,j;
    fin=fopen("energii.in","r");
    fout=fopen("energii.out","w");
    fscanf(fin,"%d%d",&G,&W);
    last=0;
    for(i=1;i<=W;++i)
		d[i]=INF;
	for(i=1;i<=W;++i)
	{
		fscanf(fin,"%d%d",&e,&c);
		for(j=last;j>=0;--j)
			if(d[j]!=INF)
				if(j+e<=W)
				{
					if(d[j+e]>d[j]+c)
					{
						d[j+e]=d[j]+c;
						if(j+e>last)
							last=j+e;
					}
				}
				else
					if(d[W]>d[j]+c)
					{
						d[W]=d[j]+c;
						last=W;
					}
	}
	if(d[W]==INF)
		fprintf(fout,"-1");
	else
		fprintf(fout,"%d\n",d[W]);
    fclose(fin);
    fclose(fout);
    return 0;
}