#include <cstdio>
#define INF 1e9
#define WMAX 5001
using namespace std;
int d[WMAX];
int main()
{
    freopen("energii.in","r",stdin);
    freopen("energii.out","w",stdout);
    int G,W,i,j,e,c,last;
    scanf("%d%d",&G,&W);
    last=0;
    for(i=1; i<=W; ++i)
        d[i]=INF;
    for(i=1; i<=W; ++i)
    {
        scanf("%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]+e)
                {
                    d[W]=d[j]+e;
                    last=W;
                }

    }
    if(d[W]==INF)
        printf("-1");
    else
        printf("%d\n",d[W]);
        return 0;
}