#include <fstream>
#define inf 5006002
using namespace std;
ifstream cin("energii.in");
ofstream cout("energii.out");
long g,w,i,j,eg,cg,fr[5002];
int main()
{
    cin>>g>>w;
    for(i=1;i<=w;i++)
        fr[i]=inf;
    fr[0]=0;
    for(i=1;i<=w;i++)
    {
        cin>>eg>>cg;
        for(j=w;j>=0;j--)
        if(j+eg<w){
            if(fr[j+eg]>fr[j]+cg)
                fr[j+eg]=fr[j]+cg;
        }
        else
            if(fr[w]>fr[j]+cg)
                fr[w]=fr[j]+cg;
    }
    if(fr[w]!=inf)
        cout<<fr[w];
    else
        cout<<-1;
    return 0;
}