#include <fstream>
#include <limits.h>
using namespace std;
ifstream fin("energii.in");
ofstream fout("energii.out");
int g,w,a[1001],b[1001],d[10001],i,j,Cmin,ok;
int main()
{
    fin>>g>>w;
    for(i=1;i<=g;i++)
        fin>>a[i]>>b[i];
    for (i=1;i<=2*w;i++)
        d[i]=-1;
    d[0]=0;
    for(i=1;i<=g;i++)
        for (j=2*w-a[i];j>=0;j--)
            if (d[j]!=-1 && d[j+a[i]] < d[j]+b[i])
                d[j+a[i]]=d[j]+b[i];

    Cmin=INT_MAX;
    for (i=2*w;i>=w;i--)
        if (d[i]!=-1)
            if(d[i]<Cmin)
                Cmin=d[i];

    fout <<Cmin;



    return 0;
}